Vorlesung im Sommersemester 2002, Dr. J. Waldmann
Mehr als Worte: Automaten und Formale Sprachen
für Bäume, Bilder und andere Strukturen
Teilnehmerkreis:
Vorlesung für Studenten der Informatik oder Mathematik im Hauptstudium,
mit Schwerpunkt Theoretische Informatik.
Übersicht:
Formale Sprachen sind Mengen von Objekten, die
- durch Grammatiken erzeugt,
- durch Logiken beschrieben,
- durch Automaten akzeptiert oder entschieden werden.
Im Informatik-Grundstudium wird dieser Zusammenhang
insbesondere für Sprachen von endlichen Wörtern erklärt.
Die Methode ist jedoch viel weitreichender.
Man interessiert sich besonders für Sprachfamilien,
für die natürliche Fragen (Wortproblem, Leere, ...) entscheidbar sind,
und natürliche Operationen (Katenation, Stern, Vereinigung, Schnitt, ...)
effektiv ausführbar. Das ist für reguläre Wortsprachen der Fall,
und das entscheidende Hilfsmittel ist ihre Darstellung durch
endliche Automaten.
In der Vorlesung werden wir diesen Automatenbegriff
verallgemeinern und damit Mengen von
- Bildern und Graphen,
- Bäumen,
- unendlichen Wörtern und Bäumen
darstellen.
Die Vorlesung hat dabei diese Schwerpunkte:
- wie akzeptiert ein endlicher Automat eine endliche Struktur?
(insbesondere: welche Konstruktionen lassen sich
von Wort- auf Baum-Automaten übertragen?)
- für welche Logiken kann man damit ein Entscheidungsverfahren
konstruieren? (Aus dem Grundkurs ist bekannt,
daß es solche Verfahren für die Aussagenlogik gibt,
für die Prädikatenlogik aber gar nicht geben kann.
Mit welchen Einschränkungen geht es aber doch?)
- welche Relationen auf Wörtern und Bäumen
lassen sich durch endliche Automaten beschreiben?
(insbesondere: welche Term-Ersetzungs-Systeme erzeugen
reguläre Nachfolgermengen?)
- wie akzeptiert ein endlicher Automat eine unendliche Struktur?
(insbesondere: wie berechnet man Komplemente?
Man kann nicht einfach akzeptierende mit ablehnenden Zuständen
vertauschen, da ein unendliches Objekt
überhaupt nicht durch Erreichen eines End-Zustandes
akzeptiert werden kann.)
Zum Teil sind die dargestellten Resultate bereits klassisch
(Büchi, Doner, Rabin, Thatcher, Wright, ca. 1970),
zum Teil benutzen wir modernere Darstellungen (Safra, Thomas, ca. 1990),
bis hin zum Anschluß an aktuelle (Comon, Dauchet, Gilleron, Jacquemard,
Lugiez, Tison, Tommasi, ca. 1999) und eigene Forschungen.
Vorkenntnisse:
Grundkurs Theoretische Informatik,
insbesondere Automaten und formale Sprachen.
Literatur:
- Hubert Comon u. a.: Tree Automata - Techniques and Applications,
- http://www.grappa.univ-lille3.fr/tata/
- Wolfgang Thomas:
Automata on Infinite Objects,
- in: v. Leeuwen (Hrsg): Handbook of Theoretical Computer Science, Band 2,
Elsevier 1990
- Wolfgang Thomas:
Languages, Automata, and Logic,
- in: Rozenberg, Salomaa (Hrsg): Handbook of Formal Languages, Band 3,
Springer 1997
