Tree-walking automaton explained

A tree-walking automaton (TWA) is a type of finite automaton that deals with tree structures rather than strings. The concept was originally proposed by Aho and Ullman.^[1]

The following article deals with tree-walking automata. For a different notion of tree automaton, closely related to regular tree languages, see branching automaton.

Definition

All trees are assumed to be binary, with labels from a fixed alphabet Σ.

Informally, a tree-walking automaton (TWA) A is a finite state device that walks over an input tree in a sequential manner. At each moment A visits a node v in state q. Depending on the state q, the label of the node v, and whether the node is the root, a left child, a right child or a leaf, A changes its state from q to q and moves to the parent of v or its left or right child. A TWA accepts a tree if it enters an accepting state, and rejects if its enters a rejecting state or makes an infinite loop. As with string automata, a TWA may be deterministic or nondeterministic.

More formally, a (nondeterministic) tree-walking automaton over an alphabet Σ is a tuplewhere Q is a finite set of states, its subsets I, F, and R are the sets of initial, accepting and rejecting states, respectively, and is the transition relation.

Example

A simple example of a tree-walking automaton is a TWA that performs depth-first search (DFS) on the input tree. The automaton

A has three states, Q = \{ q _{0} , q _{left} , q _{right} \} . A begins in the root in state q _{0} and descends to the left subtree. Then it processes the tree recursively. Whenever A enters a node v in state q _{left} , it means that the left subtree of v has just been processed, so it proceeds to the right subtree of v . If A enters a node v in state q _{right} , it means that the whole subtree with root v has been processed and A walks to the parent of v and changes its state to q _{left} or q _{right} , depending on whether v is a left or right child.

Properties

Unlike branching automata, tree-walking automata are difficult to analyze: even simple properties are nontrivial to prove. The following list summarizes some known facts related to TWA:

• As shown by Bojańczyk and Colcombet,^[2] deterministic TWA are strictly weaker than nondeterministic ones (

DTWA \subsetneq TWA )

• Deterministic TWA are closed under complementation (but it is not known whether the same holds for nondeterministic ones^[3])
• The set of languages recognized by TWA is strictly contained in regular tree languages (

TWA \subsetneq REG ), i.e. there exist regular languages that are not recognized by any tree-walking automaton, see Bojańczyk and Colcombet.^[4]

See also

• Pebble automata, an extension of tree-walking automata

External links

• Mikołaj Bojańczyk: Tree-walking automata. A brief survey.

Notes and References

1. Aho . A . Ullman . J . 10.1016/S0019-9958(71)90706-6 . Translations on a context free grammar . Information and Control . 19 . 5 . 439–475 . 1971 . free .
2. Bojańczyk . Mikołaj . Colcombet . Thomas . 10.1016/j.tcs.2005.10.031 . Tree-walking automata cannot be determinized . Theoretical Computer Science . 350 . 2–3 . 164–173 . 2006 . free .
3. Bojańczyk . Mikołaj . 2008 . Martín-Vide . Carlos . Otto . Friedrich . Fernau . Henning . Tree-Walking Automata . Language and Automata Theory and Applications . Lecture Notes in Computer Science . en . Berlin, Heidelberg . Springer . 1–2 . 10.1007/978-3-540-88282-4_1 . 978-3-540-88282-4.
4. Bojańczyk . Mikołaj . Colcombet . Thomas . 10.1137/050645427 . Tree-Walking Automata Do Not Recognize All Regular Languages . . 38 . 2 . 658–701 . 2008 .