Tree-walking automaton
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 tuple A = (Q, Σ, I, F, R, δ) where Q is a finite set of states, its subsets I, F, and R are the sets of initial, accepting and rejecting states, respectively, and δ ⊆ (Q × { root, left, right, leaf } × Σ × { up, left, right } × Q) 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 has three states, . begins in the root in state and descends to the left subtree. Then it processes the tree recursively. Whenever enters a node in state , it means that the left subtree of has just been processed, so it proceeds to the right subtree of . If enters a node in state , it means that the whole subtree with root has been processed and walks to the parent of and changes its state to or , depending on whether 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 ()
- 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 (), i.e. there exist regular languages that are not recognized by any tree-walking automaton, see Bojańczyk and Colcombet.[3]
See also
- Pebble automata, an extension of tree-walking automata
References
- ^ Aho, A; Ullman, J (1971). "Translations on a context free grammar". Information and Control. 19 (5): 439–475. doi:10.1016/S0019-9958(71)90706-6.
- ^ Bojańczyk, Mikołaj; Colcombet, Thomas (2006). "Tree-walking automata cannot be determinized" (PDF). Theoretical Computer Science. 350 (2–3): 164–173. doi:10.1016/j.tcs.2005.10.031.
- ^ Bojańczyk, Mikołaj; Colcombet, Thomas (2008). "Tree-Walking Automata Do Not Recognize All Regular Languages" (PDF). SIAM J. Comput. 38 (2): 658–701. doi:10.1137/050645427.
External links
- Mikołaj Bojańczyk: Tree-walking automata. A brief survey.