Tree Automata
Vorlesung im Wintersemester 2015/2016
Inhalt
Der Gegenstand dieser Vorlesung ist die Theorie endlicher Automaten über endliche Bäume. Wo auch immer in der Informatik mit dem Termen oder strukturierten Elementen gearbeitet wird, wie XLM Dokumente, kann diese Theorie angewendet werden. Einige Resultate sind überraschend einfach zu erhalten, nicht viel anders als bei der Theorie von Automaten über Worte. Andere Fragestellungen sind äußerst komplex und resultieren in offenen Problemen.
Wir geben eine Einführung in diese Theorie, zuerst für Bäume mit begrenzter Verzweigung, dann für Bäumen mit unbegrenzter Verzweigung - ein Fall der notwenig ist für die Theorie von XML Dokumenten Verarbeitung. Wir führen entsprechende Automaten ein und schlagen eine Brücke zur Logik, da Anfragen in logischen Systemen formuliert sind. Ausgehend von der Anfragesprache XPath untersuchen wir sequenzielle Model von Automaten die Bäume durchlaufen. Abschließend zeigen wir die Grundlagenmdoelle die für die Baumtransformation verwendet werden.
Voraussetzungen
Kentnisse der Automatentheorie, Berechenbarkeitstheorie und Logik wie sie in den Grundkursen gelehrt wird sind notwendig für die Teilnahme.
Organisation
Vortragssprache in Englisch.
Dozent