# Are non-deterministic tree-walking automata stronger than deterministic ones?

Update: It seems this problem has been studied and solved recently, see this wiki article: http://en.wikipedia.org/wiki/Tree_walking_automaton And also this survey: http://www.mimuw.edu.pl/~bojan/papers/twasurvey.pdf

Suppose that instead of the usual set of words, {0,1}*, our words are not linear but rather given on some tree structure. To prevent our machines from "getting lost", define our words as the set of binary, embedded arborescences. (So every word is a tree, where every edge is directed away from a given a root that has degree two, every other non-leaf vertex has degree three, and every edge is labeled left or right such that any two edges starting from the same vertex have different labels.) A language is a set of such trees. (Note that there is no need to write zeros and ones on the vertices as they can be anyhow simulated by locally modifying the trees.) When a machine is "reading a tree", it starts from the root, it can sense if a given vertex is the root, a leaf or a degree three vertex and can decide if in the next step it wants to go to the parent of the vertex, or on the edge labeled left or right.

Is it true in this model that any language that can be recognized by a non-deterministic finite state automaton can also be recognized by a deterministic finite state automaton?

Note that when the tape is the usual linear tape, this is true, as any 2-NFA can be simulated with a 2-DFA (even with a DFA). I already asked a special instance of the problem here that was solved by Kristoffer. The motivation would be to solve this.

• I would suggest modifying the title to mention "non-deterministic tree-walking automata". – Sylvain May 9 '11 at 9:20

## 2 Answers

For tree automata, you have the following results:

• Deterministic bottom-up tree automata have the same expressive power as non-deterministic bottom-up tree automata.

• Deterministic top-down tree automata are weaker than non-deterministic top-down tree automata.

More details can be found in the Tree Automata book.

It seems that you are interested in top-down tree automata, so the answer to your question is no. You will of course have to check whether top-down tree automata are in fact what you are interested in.

Yes/No = Non-deterministic automata are stronger: http://www.mimuw.edu.pl/~bojan/papers/dtwa.pdf