Tree-walking automaton

A tree walking automaton (TWA) is a type of finite automaton that deals with tree structures rather than strings.

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 $\Sigma$.

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 $\Sigma$ is a tuple: $A=(Q,\Sigma ,I,F,R,\delta )$

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

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 3 states, $Q=\{q_{0},q_{\mathit {left}},q_{\mathit {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_{\mathit {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_{\mathit {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_{\mathit {left}}$ or $q_{\mathit {right}}$, depending on whether $v$ is a left or right child.

The resulting automaton is the following: File:Twa-dfs.png

Properties

Unlike 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 Bojanczyk & Colcombet (2006), deterministic TWA are strictly weaker than nondeterministic ones (${\mathit {DTWA}}\subsetneq {\mathit {TWA}}$)
• 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 (${\mathit {TWA}}\subsetneq {\mathit {REG}}$), i.e. there exist regular languages which are not recognized by any tree walking automaton (Bojanczyk & Colcombet 2008).

See also

• Pebble automata, an extension of tree walking automata

External links

• Mikołaj Bojanczyk: Tree-walking automata. A brief survey.