Bibliography | Göggelmann, Manuel: Effiziente Algorithmen für das Separierbarkeitsproblem der alternierungsfreien Logik über unendlichen Wörtern. University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 30 (2015). 33 pages, german.
|
CR-Schema | F.4.1 (Mathematical Logic) F.4.3 (Formal Languages)
|
Abstract | 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.
|
Full text and other links | PDF (398228 Bytes)
|
Department(s) | University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
|
Superviser(s) | Kufleitner, PD Dr. Manfred |
Entry date | November 16, 2018 |
---|