Tree walking automaton

From Wikipedia, the free encyclopedia

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.

1 Definition
2 Example
3 Properties
4 See also

[edit] Definition

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

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

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

[edit] 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 l e f t, q r i g h t /$ . $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 l e f t$ , 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 r i g h t$ , 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 l e f t$ or $q r i g h t$ , depending on whether $v$ is a left or right child.

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

[edit] Properties

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

deterministic TWA are strictly weaker than nondeterministic ones ( $DTWA \subsetneq TWA$ )
deterministic TWA are closed under complementation; 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 ( $TWA \subsetneq REG$ ), i.e. there exists a regular language which is not recognized by any tree walking automaton