A tree

Tree Automata Techniques and Applications

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:

Contents


For any comment on this site: Marc Tommasi .