Deterministic Automata on Unranked Trees

Abstract. We investigate bottom-up and top-down deterministic au-tomata on unranked trees. We show that for an appropriate denition of bottom-up deterministic automata it is possible to minimize the number of states eciently and to obtain a unique canonical representative of the accepted tree language. For top-down deterministic automata it is well known that they are less expressive than the non-deterministic ones. By generalizing a corresponding proof from the theory of ranked tree au-tomata we show that it is decidable whether a given regular language of unranked trees can be recognized by a top-down deterministic au-tomaton. The standard deterministic top-down model is slightly weaker than the model we use, where at each node the automaton can scan the sequence of the labels of its successors before deciding its next move.