Technical Report No. 2011-577 State Complexity of Star and Quotient Operation for Unranked Tree Automata
Xiaoxue Piao, Kai Salomaa · 2011
We consider the state complexity of extensions of the Kleene star and quotient operations to unranked tree languages. Due to the na- ture of the tree structure, there are two distinct ways to define the star operation for trees, we call these operations, respectively, bottom-up and top-down star. We show that (n + 3 )2 n−1 states are sufficient and nec- essary in the worst case to recognize the bottom-up star of a tree lan- guage recognized by an n-state deterministic unranked tree automaton. The bound is of a different order than the known state complexity re- sult 3 · 2 n−1 for the Kleene star operation for automata on strings. On the other hand, for the top-down star we obtain a tight state complex- ity bound that coincides with the corresponding result for automata on strings. The bottom-quotient and top-quotient operations are extensions of the left and right quotient to trees. We establish tight state complexity bounds for both variants of quotient. The precise worst-case state com- plexity of bottom-quotient is shown to be (n+1)2 n 1, which differs by the multiplicative factor n + 1 from the corresponding result 2 n 1 for ordinary finite automata.