Mikołaj Bojańczyk, Thomas Colcombet
Tree-walking automata cannot be determinized. Theor. Comput. Sci., 2006 PDF
Mikołaj Bojańczyk, Thomas Colcombet
Tree-Walking Automata Do Not Recognize All Regular Languages. SIAM J. Comput., 2008 PDF
Mikołaj Bojańczyk
Tree-Walking Automata. LATA, 2008 PDF
A tree-walking automaton is a natural model of automaton for trees. If you would be absolutely fixed on the idea that an automaton must have a single head, then this is the model you would come up with. The idea is that the automaton has a single head, and traverses the tree by going up and down, typically doing something like a depth-first search. This is a series of papers devoted to showing that the model is not well-behaved. The first paper shows they cannot be determinised, the second that they are strictly weaker than the classical model of branching tree automata, and the third is a survey of the topic.
My adventure with tree-walking automata started with this paper:
Mikołaj Bojańczyk
1-Bounded TWA Cannot Be Determinized. FSTTCS, 2003 PDF
which showed what it’s title says (a 1-bounded tree-walking automaton is one which traverses every tree edge once in each direction, generalising in depth-first search). This paper started the technique of using semigroups for more fancy pumping, a technique which was used in the follow-up papers.
The breakthrough came when Thomas Colcombet and I started collaborating. We proved that arbitrary tree-walking automata cannot be determinised
Mikołaj Bojańczyk, Thomas Colcombet
Tree-Walking Automata Cannot Be Determinized. ICALP, 2004
and then, using the essentially the same techniques but a lot more of pages, that even nondeterministic tree-walking automata are strictly weaker than the “proper” model of tree automata, namely branching automata:
Mikołaj Bojańczyk, Thomas Colcombet
Tree-walking automata do not recognize all regular languages. STOC, 2005 PDF
The journal versions of the two papers above are mentioned at the beginning of this post.
Leave a Reply