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.
