Tree Automata | Baum-Automaten
Waldmann, Johannes
Audience:
students of computer science interested in theory
Overview:
The study of formal languages is one of the oldest topics in theoretical computer science. It has led to a well understood theory with lots of deep and beautiful results. The fundamental concepts of which are grammars that produce words, and automata that accept words.
However, words are not appropriate to represent data with hierarchical structure. These should better be modelled by trees. Therefore we are interested in tree languages.
Among word languages, the regular languages are quite handsome. They can be recognised by finite automata, and there are effective algorithms for operations on finite automata.
We will define the analogous concept of regular tree language and finite tree automaton, and develop their theory. In many cases, results and methods on word languages carry over to tree languages; but in some other cases we need new ideas. This also serves to revive the audience's knowledge and understanding of word languages.
Finally we mention a recent application of tree automata techniques to term rewriting: successor sets of rewrite systems can, under certain circumstances, be approximated by regular tree languages. This is applicable in the analysis and verification of programs.
Literature:
Prerequisites:
basic course on formal languages and automata
Credits:
for active participation
Additional information: