View source for Fourt–Woodlock equation

A '''tree walking automaton''' (TWA) is a type of [[finite automaton]] that deals with [[tree structure]]s rather than strings. The concept was originally proposed in {{harvtxt|Aho|Ullman|1971}}.

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

==Definition==

All trees are assumed to be binary, with labels from a fixed alphabet <math>\Sigma</math>.

Informally, a tree walking automaton A (TWA) is a finite state device which walks over the tree in a sequential manner. At each moment A visits 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 alphabet <math>\Sigma</math> is a tuple:
<math>A=(Q, \Sigma, I, F, R, \delta)</math>

where <math>Q</math> is a finite set of states, <math>I, F, R \subset Q</math> are the sets of respectively initial, accepting and rejecting states, and <math>\delta</math> is the transition relation: <math>\delta \subset (Q \times \{ \mathit{root}, \mathit{left}, \mathit{right},\mathit{leaf} \} \times \Sigma \times \{ \mathit{up}, \mathit{left}, \mathit{right} \} \times Q)</math>.

==Example==

A simple example of a tree walking automaton is a TWA that performs [[depth-first search]] (DFS) on the input tree. The automaton <math>A</math> has 3 states, <math>Q = \{ q_{0}, q_{\mathit{left}}, q_{\mathit{right}} \}</math>. <math>A</math> begins in the root in state <math>q_{0}</math> and descends to the left subtree. Then it processes the tree recursively. Whenever <math>A</math> enters a node <math>v</math> in state <math>q_{\mathit{left}}</math>, it means that the left subtree of <math>v</math> has just been processed, so it proceeds to the right subtree of <math>v</math>. If <math>A</math> enters a node <math>v</math> in state <math>q_{\mathit{right}}</math>, it means that the whole subtree with root <math>v</math> has been processed and <math>A</math> walks to the parent of <math>v</math> and changes its state to <math>q_{\mathit{left}}</math> or <math>q_{\mathit{right}}</math>, depending on whether <math>v</math> is a left or right child.

==Properties==

Unlike [[tree automaton|branching automata]], tree walking automata are difficult to analyze and even simple properties are nontrivial to prove. The following list summarizes some known facts related to TWA:
*As shown by {{harvtxt|Bojanczyk|Colcombet|2006}}, deterministic TWA are strictly weaker than nondeterministic ones (<math>\mathit{DTWA} \subsetneq \mathit{TWA}</math>)
*deterministic TWA are closed under complementation (but it is not known whether the same holds for nondeterministic ones)
*the set of languages recognized by TWA is strictly contained in regular tree languages (<math>\mathit{TWA} \subsetneq \mathit{REG}</math>), i.e. there exist regular languages which are not recognized by any tree walking automaton {{harv|Bojanczyk|Colcombet|2008}}.

==See also==

*[[Pebble automaton|Pebble automata]], an extension of tree walking automata

==References==
* {{cite doi|10.1016/S0019-9958(71)90706-6}}
* {{cite doi|10.1016/j.tcs.2005.10.031}}
* {{cite doi|10.1137/050645427}}

==External links==
*Mikołaj Bojanczyk: [http://www.mimuw.edu.pl/~bojan/papers/twasurvey.pdf Tree-walking automata]. A brief survey.

[[Category:Trees (data structures)]]
[[Category:Automata theory]]