Student Thesis STUD-2425

BibliographyMüller, Sebastian: Deterministische endliche Automaten und Zwei-Variablen-Logik erster Stufe.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Student Thesis No. 2425 (2013).
22 pages, german.
CR-SchemaF.4.3 (Formal Languages)
Abstract

Therien und Wilke zeigten in einer Arbeit von 1998, dass 2-Variablen-Logik erster Stufe (FO^2) einer entscheidbaren Klasse endlicher Monoide entspricht. Damit läßt sich insbesondere für jede reguläre Sprache entscheiden, ob sie in FO^2 definierbar ist. Dieses Entscheidbarkeitsresultat konnte 2012 in einer Arbeit von Weil und Kufleitner auf die Alternierungshierarchie innerhalb von FO^2 ausgedehnt werden. Im Rahmen dieser Arbeit wird untersucht, wie effizient sich diese Entscheidbarkeitsresultate umsetzen lassen, wenn die reguläre Sprache durch deterministische endliche Automaten gegeben ist. Als Vorstufe hierzu werden geeignete algebraische Charakterisierungen der Alternierungshierarchie innerhalb von FO^2 recherchiert. Basierend darauf werden Entscheidungsverfahren auf Basis sogenannter Verbotsmuster entwickelt.

Full text and
other links
PDF (381386 Bytes)
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Superviser(s)Kufleitner, Manfred
Entry dateMarch 10, 2014
   Publ. Computer Science