Lecture in Winter Term 2015/2016
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.
Knowledge of automata theory, computability theory and logic as presented in basic courses is required for participation.
Lecture will be held in english.