Bachelorarbeit BCLR-0061

Bibliograph.
Daten
Rupp, Tobias: Verbotmuster bei deterministischen endlichen Automaten in der Trotter-Weil-Hierarchie.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 61 (2013).
42 Seiten, deutsch.
CR-Klassif.F.4.3 (Formal Languages)
Kurzfassung

Die Klasse DA von endlichen Monoiden besitzt eine Vielzahl an Charakterisierungen logischer, kombinatorischer und algebraischer Art. Unter anderem bildet DA eine sogenannte Varietät. Um die Struktur der Untervarietäten von DA zu untersuchen, betrachteten Trotter und Weil den Schnitt mit idempotenten Halbgruppen. Da deren Hierarchie bereits bekannt war, führte dies zu einer neuen Varietätenhierarchie innerhalb von DA, der Trotter-Weil-Hierarchie. Überdies konnten für diese Varietäten algebraische Charakterisierungen angegeben werden, die Entscheidbarkeit ermöglichten. Falls nun eine Sprache in der Form eines deterministischen endlichen Automaten gegeben ist, soll effizient entschieden werden können, ob das syntaktisches Monoid in einer gegebenen Varietät der Trotter-Weil-Hierarchie liegt. In dieser Bachelorarbeit werden unter Verwendung von Verbotsmustern entsprechende Entscheidungsalgorithmen der Komplexitätsklassen NL und P konstruiert. Verbotsmuster bezeichnen hierbei Graphkonfigurationen, die im Automatengraph nicht vorkommen dürfen.

Volltext und
andere Links
PDF (353349 Bytes)
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
BetreuerKufleitner, Manfred
Eingabedatum21. November 2013
   Publ. Informatik