Logic and
Theory of
Discrete Systems

Informatik 7

Tree Automata

Lecture in Winter Term 2015/2016

This course is given in English.

V2 Thu 10:15–11:45, Raum 4116 (Seminarraum i7) Löding Campus link
Ü1 Wed 11:00–12:00, Raum 4116 (Seminarraum i7) LödingWinter Campus link

The first lecture will take place on Thursday, October 22.
The first tutorial will take place on Wednesday, November 4.


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.

Previous Knowledge

Knowledge of automata theory, computability theory and logic as presented in basic courses is required for participation.