Titel: Einfache Logikfragmente mit Nachfolgerrelation über unendlichen Wörtern Author: Jonathan Kausch

Die sternfreien Sprachen stellen eine wichtige Unterklasse der regulären Sprachen dar. Sie sind reguläre Ausdrücke, die ohne Stern, aber mit Komplementbildung definiert werden können. Über die Anzahl der Konkatenationen erhält man die Tiefe der sogenannten Dot-Depth Hierarchie. Die erste Stufe der Dot-Depth Hierarchie entspricht booleschen Kombinationen von prädikatenlogischen Formeln (FO) in Pränexnormalform ohne Quantorenalternierung (d.h. mit nur einem Block von Quantoren) mit [<,+1,min,max]. Eine algebraische Eigenschaft für die Stufe 1 der Dot-Depth Hierarchie wurde von Knast für endliche Wörter gefunden. Mit zusätzlichen topologischen Eigenschaften lassen sich die Resultate auf unendliche Wörter übertragen.

In dieser Arbeit wird die, von Knast gefundene, Eigenschaft erstmalig auf unendliche Wörter übertragen. Wie sich herausstellt, liefert diese Eigenschaft selbiges Logikfragment von Formeln ohne Quantorenalternierung mit [<,+1,min]. Außerdem wird ein vereinfachter Beweis des sogenannten Wreath-Product-Principles vorgestellt, welches eine direkte Beziehung von Formeln mit [<,+1,min,max] zu Formeln mit nur [<] herstellt.