Verbotsmuster bei deterministischen endlichen Automaten in der Trotter-Weil-Hierarchie

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.