*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion 16
Dienstag, 19.09.2000, 14.30–14.50 Uhr, WIL C 307

Monadisch axiomatisierbare Mengen unendlicher N-freier Ordnungen

Dietrich Kuske, TU Dresden, Institut für Algebra

In der theoretischen Informatik existieren verschiedene Charakterisierungen der durch endliche Automaten akzeptierbaren Mengen von Wörtern: Insbesondere ist dies durch rationale Ausdrücke (Kleene), algebraische (Myhill-Nerode) und logische (BÜchi) Methoden möglich. Diese Zusammenhänge sind auch für unendliche Wörter und für Bäume untersucht worden. Seit längerem gibt es ein steigendes Interesse im Rahmen der Theorie nebenläufiger Prozesse, ähnliche Charakterisierungen für Klassen partiell geordneter Mengen zu erhalten. In diesem Vortrag untersuchen wir N-freie beschriftete Ordnungen, die nur endliche Antiketten und endliche Hauptfilter enthalten. Dies sind genau die Ordnungen, die sich durch das serielle und das parallele Produkt (angewandt u.U. auf abzählbar viele endliche Argumente) erzeugen lassen. Für eine uniform weitenbeschränkte Menge solcher Ordnungen wird gezeigt, dass sie genau dann monadisch axiomatisierbar ist, wenn sie w-seriell-rational ist. Außerdem wird eine algebraische Charakterisierung dieser Mengen angegeben. Diese Ergebnisse erweitern kürzlich erhaltene Resultate von Lodaya und Weil in zwei Richtungen: Teile ihrer Resultate werden auf unendliche geordnete Menge ausgedehnt, und ihr Bild wird durch die Betrachtung logisch axiomatisierbarer Mengen abgerundet.