Tree-Walking Automata Do Not Recognize All Regular Languages
Mikołaj Bojańczyk, Thomas Colcombet · SIAM Journal on Computing · 2008
Tree-walking automata are a natural sequential model for recognizing tree languages. It is well known that every tree language recognized by a tree-walking automaton is regular. We show that the converse does not hold.