Monotone AC-tree automata

Abstract. We consider several questions about monotone AC-tree automata, a class of equational tree automata [21] whose transition rules correspond to rules in Kuroda normal form of context-sensitive grammars. Whereas it is known that this class has a decision procedure to determine if a given monotone AC-tree automaton accepts no term [23], other decidability and complexity results have not been well-investigated yet. In the paper, we prove that the membership prob-lem for monotone AC-tree automata is PSPACE-complete. We then study the expressiveness of monotone AC-tree automata: precisely, we prove that the fam-ily of AC-regular tree languages is strictly subsumed in that of AC-monotone tree languages. This result immediately yields the answers to two open problems, specially that the family of monotone AC-tree languages is not closed under com-plementation, and that the inclusion problem for monotone AC-tree automata is undecidable