Lower bounds for the size of deterministic unranked tree automata (Q714828)

In an unranked tree a node labeled with a given input symbol may have any number of children. Therefore, the state transitions of a finite bottom-up automaton operating on such trees are defined by regular string languages over the state alphabet. These languages, one for each input symbol, are defined by finite automata. Hence the tree automaton has two kinds of states, the vertical states used in the bottom-up main computation and the horizontal states used for computing the vertical state transitions. Both the vertical and the horizontal behavior may be either deterministic or nondeterministic. In general, the deterministic bottom-up tree automaton with the minimal total number of states recognizing a given regular unranked tree language is not unique, and finding lower bounds for the total number of states is hard. In this paper the authors give an improved lower bound for the size blow-up resulting from the determinization of a nondeterministic unranked tree automaton.