Complementing deterministic tree-walking automata

Anca Muscholl (1) , Mathias Samuelides (1) , Luc Segoufin (2)

1 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications
2 GEMO - Integration of data and knowledge distributed over the web

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.

Domaines: Informatique et langage [cs.CL]

Anca Muscholl, Mathias Samuelides, Luc Segoufin. Complementing deterministic tree-walking automata. Information Processing Letters, 2006, 99 (1), pp.33 - 39. ⟨hal-00158657⟩