Recognizable Tree Languages and Finite Tree Automata
Trees
Finite Tree Automata deal with finite ordered ranked trees which correspond to finite terms over a ranked alphabet. For finite ordered trees with a known bound on the out-degrees of internal nodes, finite ordered trees can be encoded in finite ordered ranked trees. When there is no bound on the out-degrees of internal nodes, trees are finite ordered unranked trees. Unranked trees are used for XML Document Type Definitions and more generally for XML schema languages. All the fundamental results for finite tree automata can be extended to the case of unranked trees with the help of hedge automata. An other extension is to consider unordered trees. Unordered trees are discussed in Section 4 because they are related to tree automata modulo equational theories. We plan the redaction of a new chapter covering Tree Automata for Unranked Trees, Unordered Trees and more generally Tree Automata for Trees modulo Equational Theories.Finite Automata vs Finite Tree Automata
The theory of Tree Automata is a straightforward extension of the theory of word automata when words are viewed as unary terms. There are two main differences between the tree case and the word case:- left-to-right and right-to-left automata are equivalent in the word case but bottom-up and top-down tree automata differ: deterministic top-down tree automata are strictly less powerful than non determinstic ones.
- recognizable (word) languages are closed under (word) homomorphisms but recognizable tree languages are closed under linear tree homomorphisms where duplication of trees is forbidden.
Contents
- Finite Tree Automata
- The Pumping Lemma for Recognizable Tree Languages
- Closure Properties of Recognizable Tree Languages
- Tree Homomorphisms
- Minimizing Tree Automata
- Top Down Tree Automata
- Decision Problems and their Complexity
- Exercises
- Bibliographic Notes