Bachelor Thesis BCLR-0061

BibliographyRupp, Tobias: Verbotmuster bei deterministischen endlichen Automaten in der Trotter-Weil-Hierarchie.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 61 (2013).
42 pages, german.
CR-SchemaF.4.3 (Formal Languages)
Abstract

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.

Full text and
other links
PDF (353349 Bytes)
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Superviser(s)Kufleitner, Manfred
Entry dateNovember 21, 2013
   Publ. Computer Science