Mikołaj Bojańczyk

Tree-walking automata

May 17, 2015
  1. Mikołaj Bojańczyk, Thomas Colcombet
    Tree-walking automata cannot be determinized. Theor. Comput. Sci., 2006   PDF

  2. Mikołaj Bojańczyk, Thomas Colcombet
    Tree-Walking Automata Do Not Recognize All Regular Languages. SIAM J. Comput., 2008   PDF

  3. 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

Your email address will not be published.