Master Thesis MSTR-2018-38

BibliographyHanke, Carlos: Charakterisierung strukturell einfacher Quantorenalternierungen.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Master Thesis No. 38 (2018).
36 pages, german.
Abstract

Band-Varietäten, also Varietäten idempotenter Halbgruppen, sind bereits seit langem vollständig klassifiziert [1]. Durch Trotter und Weil wurden, darauf aufbauend, andere Varietäten in DA untersucht, indem der Durchschnitt mit einer Band-Varietät betrachtet wurde. Dadurch sind dann Rückschlüsse auf die Varietät möglich. Fur jede Band-Varietät V existiert dann eine maximale Varietät in DA deren Schnitt mit der Varietät aller Band-Monoide wieder V ergibt. Auf diese Weise erhält man auf den Varietäten in DA eine den Bands entsprechende Hierarchie, die Trotter-Weil-Hierarchie [2]. Diese wurde oft untersucht und es wurden viele weitere Eigenschaften und Charakterisierungen herausgearbeitet. So etwa der Zusammenhang mit der Quantorenalternierung innerhalb der Zwei-Variablen-Logik erster Stufe [3][4]. Hierfür existiert eine äquivalente, auf Blockprodukten basierende, Beschreibung von Krebs und Straubing. Als Resultat daraus lässt sich innerhalb der Trotter-Weil-Hierarchie entlang der Schnittlevel, durch Blockprodukte mit J-trivialen Monoiden, aufsteigen [5]. Darauf aufbauend sollen in dieser Arbeit die dafür nötigen Grundlagen gesammelt werden und ein erster Versuch gewagt werden, eine ähnliche Methode auch für die Vereinigungslevel zu finden.

Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Superviser(s)Kufleitner, PD Dr. Manfred; Fleischer, Lukas
Entry dateJune 3, 2019
   Publ. Institute   Publ. Computer Science