Vortragsankündigung, Bereichsseminar Theoretische Informatik,
Dienstag, den 24. 4. 2001, 15:15 - 16:45, Hauptgebäude Raum 3-68
Johannes Waldmann, Institut für Informatik, Universität Leipzig

Automaten, die auf Bäumen spazierengehen


Die klassische Theorie formaler Sprachen und Automaten untersucht Mengen von Wörtern. Viele Daten haben jedoch eine hierarchische Struktur, und man erforscht deswegen Baum-Sprachen.

Eine naheliegende Verallgemeinerung von regulären (d. h. links-linearen) Wort-Grammatiken führt zur Klasse der regulären Baum-Sprachen. Man möchte das Bild abrunden durch eine dazu passende Klasse von Automaten.

Nun enthält ein Baum mehrere Teilbäume, und ein Automat kann diese nacheinander (sequentiell) oder gleichzeitig (parallel) durchlaufen. Während das parallele Modell gut untersucht ist, herrscht noch keine Einigkeit über das sequentielle Pendant. Im Vortrag berichte ich über Arbeiten zu diesem Thema von Joost Engelfriet und Hendrik Jan Hoogeboom.

Sequentielle Automaten mit endlichem Speicher, die auf Bäumen spazierengehen, können sehr wahrscheinlich nicht alle regulären Baumsprachen akzeptieren. Man gestattet deswegen diesen Automaten, im Baum Markierungen (pebbles) anzubringen.

Es ist bis heute nicht genau bekannt, wie sehr sich durch Pebbles die Rechenkraft erhöht. Die Klasse der damit akzeptierbaren Sprachen ist jedenfalls eine Teilklasse der regulären Baumsprachen, und enthält die Klasse der First-Order-definierbaren Baumsprachen. Man vermutet, daß die erstgenannte Inklusion strikt ist.


Literatur
Zum Verständnis des Vortrags sind Grundkenntnisse über endliche Wort-Automaten ausreichend. Ich lade deswegen insbesondere das 4. Semester herzlich ein. Zu einigen Beispielen werde ich autotool-Skripte anfertigen.
http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de