In this project, we aim to develop taxonomies and toolkits of tree algorithms. In particular, three types of tree algorithms seem interesting:
- algorithms for tree pattern matching
- algorithms for acceptance of trees
- algorithms for parsing trees
The concept of finite tree automata plays a central role here. Such automata form a generalization of finite automata on strings. Many algorithms for the above problems use some form of tree automata.
Although a lot of theory and practical experience for the field is available, a coherently structured classification is lacking. Parts of the theory have been around for a long time, but even though the theory might be old, the applications of tree automata are not outdated at all: algorithms of the kind mentioned above are used in applications such diverse as code generation and optimization, XML document processing, term rewriting, type inference, genetics (DNA/RNA pattern matching) and cryptography. |