Bibliograph. Daten | Göggelmann, Manuel: Effiziente Algorithmen für das Separierbarkeitsproblem der alternierungsfreien Logik über unendlichen Wörtern. Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 30 (2015). 33 Seiten, deutsch.
|
CR-Klassif. | F.4.1 (Mathematical Logic) F.4.3 (Formal Languages)
|
Kurzfassung | Das Separierbarkeitsproblem befasst sich mit der Frage, gegeben zwei Mengen aus einer Klasse, ob es möglich ist, sie durch eine weitere Menge aus einer kleineren Klasse zu separieren. Für den Fall der Separierbarkeit von regulären Sprachen durch eine piecewise testable Sprache über unendlichen Wörtern wird in dieser Arbeit ein Entscheidungsalgorithmus mit polynomialer Laufzeit vorgestellt. Der Beweis orientiert sich an einer Arbeit über den entsprechenden Fall der Separierbarkeit über endlichen Wörtern von L. van Rooijen und M. Zeitoun.
|
Volltext und andere Links | PDF (398228 Bytes)
|
Abteilung(en) | Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
|
Betreuer | Kufleitner, PD Dr. Manfred |
Eingabedatum | 16. November 2018 |
---|