Titel: Logik erster Stufe ohne Quantorenalternierung über endlichen Wörtern Author: Martin P. Seybold Prüfer: Prof. Dr. V. Diekert Betreuer: Dr. M. Kufleitner

Sternfreie Sprachen sind eine wichtige Unterklasse der regulären Sprachen. Sie Entstehen durch Konkatenation und Komplementierung von Ausdrücken, die keinen Kleene Stern enthalten. Die minimal benötigte Anzahl von Konkatenationen, sprich das Level in der Dot-Depth Hierarchie, einer gegebenen Sprache zu bestimmen ist eine Herausforderung der Automatentheorie. Wörter kann man auch als lineare Anordnung von Buchstaben interpretieren. Dadurch erscheint es sinnvoll Muster durch prädikatenlogische Formeln, bezüglich Position und Beschriftung, zu definieren. Es ist bekannt, dass die durch Prädikatenlogik erster Stufe definierbaren Sprachen genau die sternfreien Sprachen sind. Durch Einschränkung auf bestimmte Prädikate, Variablenzahl oder Quantorenalternierungen ergeben sich auf natürliche Weise Hierarchien dieser Logikfragmente. Es ist auch bekannt, dass die Zahl der Quantorenalternierungen mit der Zahl benötigter Konkatenationen zusammenhängt. Bisher ist nur die Stufe 1 der Dot-Depth Hierarchie algorithmisch entscheidbar.

In dieser Arbeit werden Logikfragmente ohne Quantorenalternierung, jedoch mit den Prädikaten <, +1, min oder max, untersucht. Wir geben einen neuen, elementaren Beweis für Dot-Depth 1 an. Außerdem geben wir für die Fragmente ohne min oder max Prädikate algorithmisch entscheidbare Charakterisierungen an, wobei es sich hierbei um neue Ergebnisse handelt.