Complementing deterministic tree-walking automata
We consider various kinds of deterministic tree-walking automata, with and without pebbles, over ranked and unranked trees. For 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. (c) 2006 Elsevier B.V All rights reserved.
combinatorial problems formal languages tree-automata