Tree Automata
» Diese Veranstaltung wird auf englisch gehalten.
» Es gibt einen L2P-Lernraum zu dieser Veranstaltung.
Lecture in Winter Term 2011/12
| Type | Time/Place | Start | Lecturer |
|---|---|---|---|
| V2 | Tue 11:45–13:15, 5056 | 11 October 2011 | Löding |
| Ü1 | Fri 10:00–11:00, 4116 | 21 October 2011 | Löding, Spelten, Lang |
Preliminary Information:
Contents
The subject of this course is the theory of finite automata over finite trees. Wherever in computer science one deals with terms or structured objects (such as XML documents) one can use concepts of this theory. Some results are surprisingly easily obtained in analogy to the standard theory of automata over words. Other questions are highly complex and lead to open problems.
We give an introduction to this theory, first for trees with bounded branching, then for trees with unbounded branching - a case that is needed in the theory of XML-document processing. We introduce corresponding models of automata and establish a bridge to logic (since queries are formulated in logical systems). Motivated by the query language XPath we study the sequential model of tree walking automaton. Finally we present the fundamental models used for tree transformation.
Credit Points
4 ECTS