Bachelor Thesis BCLR-2013-10

BibliographyFleischer, Lukas: Algebraische Charakterisierungen von positiver Quantorenalternierung bei Zwei-Variablen-Logik.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 10 (2013).
39 pages, german.
Abstract

Thérien und Wilke zeigten in einer Arbeit von 1998, dass Zwei-Variablen-Logik erster Stufe (FO2) einer entscheidbaren Klasse endlicher Monoide entspricht. Insbesondere lässt sich damit für jede reguläre Sprache entscheiden, ob sie in FO2 definierbar ist. Dieses Entscheidbarkeitsresultat konnte im vergangenen Jahr von Weil und Kufleitner auf die Alternierungshierarchie innerhalb von FO2 ausgedehnt werden. In einer aktuellen Arbeit von Lauser und Kufleitner wurde dieses Ergebnis noch weiter verfeinert. Sie konnten zeigen, dass die positive Alternierungshierarchie innerhalb von FO2 entscheidbar ist. Krebs und Straubing konnten mit einem anderen Zugang ebenfalls das Entscheidbarkeitsresultat von Weil und Kufleitner beweisen. Anstelle von sogenannten Rankern basiert ihre Charakterisierung auf Blockprodukten. In dieser Arbeit wird diese Technik auf die positive Alternierungshierarchie übertragen. Es werden verschiedene, auf Blockprodukten basierende, algebraische Charakterisierungen der Level der positiven Alternierungshierarchie vorgestellt und deren Entscheidbarkeit bewiesen.

Full text and
other links
Volltext
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Superviser(s)Diekert, Prof. Volker; Kufleitner, Dr. Manfred
Entry dateFebruary 26, 2020
New Report   New Article   New Monograph   Computer Science