Diplomarbeit DIP-2775

Bibliograph.
Daten
Baumann, Thomas: Quantorenalternierung und reguläre Sprachen.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Diplomarbeit Nr. 2775 (2008).
37 Seiten, deutsch.
CR-Klassif.F.4.3 (Formal Languages)
Keywordsformale Sprachen, reguläre Ausdruecke, dot-depth Hierarchie
Kurzfassung

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.

Volltext und
andere Links
PDF (328080 Bytes)
PostScript (572538 Bytes)
Zugriff auf studentische Arbeiten aufgrund vorherrschender Datenschutzbestimmungen nur innerhalb der Fakultät möglich
CopyrightThomas Baumann
Kontakttombau@t-online.de
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
BetreuerKufleitner, Manfred
Eingabedatum13. März 2009
   Publ. Informatik