PEBBLE TREE AUTOMATA
Mathias Samuelides, Anca Muscholl · OpenGrey (Institut de l'Information Scientifique et Technique) · 2007
Two variants of pebble tree-walking automata on binary trees are considered that were introduced in the literature. For the deterministic variant of each such kind of automata we show that there is an equivalent one which never loops. The main consequence of this result is the closure under complementation of the various types of automata we consider with a focus on the number of pebbles used in order to complement the automata. It is shown that for each number of pebbles, the two models have the same expressive power both in the deterministic case and in the nondeterministic case. Furthermore, nondeterministic (resp. deterministic) tree-walking automata with n+1 pebbles can recognize more languages than those with npebbles. Moreover, there is a regular tree language that is not recognized by any tree-walking automaton with pebbles. As a consequence, FO+posTC is strictly included in MSO over trees. Finally, for each k, we give the precise complexities of the problems of emptiness and inclusion of tree-walking automata using k pebbles.