Bibliography | Baumann, Thomas: Quantorenalternierung und reguläre Sprachen. University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Diploma Thesis No. 2775 (2008). 37 pages, german.
|
CR-Schema | F.4.3 (Formal Languages)
|
Keywords | formale Sprachen, reguläre Ausdruecke, dot-depth Hierarchie |
Abstract | Seit den 1960er Jahren befindet sich die Dot-Depth Hierarchie von Brzozowski und Cohen im Zentrum der Erforschung sternfreier regulärer Sprachen. Sie bildet in diesen eine strikte Hierarchie, deren Vereinigung gerade die sternfreien Sprachen ergibt und die bis zum heutigen Tage trotz einiger erstaunlicher Teilresultate nur auf den untersten Ebenen vollständig verstanden wird.
Die vorliegende Arbeit befasst sich mit einem Resultat von Straubing aus dem Jahre 1988, das die Entscheidbarkeit der zweiten Stufe dieser Hierarchie für Sprachen mit maximal zwei Erzeugern nachweist. Insbesondere wird dieses Resultat im Licht neuerer Erkenntnisse der algebraischen Sprachentheorie betrachtet und eine notwendige Bedingung für das Enthaltensein in einer bestimmten Klasse von Monoiden erarbeitet. Abschließend wird diese verwendet um einen neuen Gegenbeweis einer Vermutung, über die Struktur der zweiten Stufe von Brzozowskis Hierarchie, aus dem Jahre 2001 zu widerlegen.
|
Full text and other links | PDF (328080 Bytes) PostScript (572538 Bytes) Access to students' publications restricted to the faculty due to current privacy regulations |
Copyright | Thomas Baumann |
Contact | tombau@t-online.de |
Department(s) | University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
|
Superviser(s) | Kufleitner, Manfred |
Entry date | March 13, 2009 |
---|