Mikołaj Bojańczyk

May 17, 2015

Mikołaj Bojańczyk, Thomas Colcombet

*Tree-walking automata cannot be determinized.*Theor. Comput. Sci., 2006 PDFMikołaj Bojańczyk, Thomas Colcombet

*Tree-Walking Automata Do Not Recognize All Regular Languages.*SIAM J. Comput., 2008 PDFMikoł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