Skip to Main content Skip to Navigation
Conference papers

Monotone AC-Tree Automata

Abstract : This paper considers several questions about monotone AC-tree automata, a class of equational tree automata whose transition rules correspond to rules in Kuroda normal form of context-sensitive grammars. Whereas it has been proved that this class has a decision procedure to determine if, given a monotone AC-tree automaton, it accepts no terms, other important decidability or complexity results have not been well-investigated yet. In the paper, it is proved that the membership problem for monotone AC-tree automata is PSPACE-complete. The expressiveness of monotone AC-tree automata is also studied: precisely, it is proved that the family of AC-regular tree languages is strictly subsumed in that of AC-monotone tree languages. The proof technique used in obtaining the above result yields the answers to two different questions, specifically that the family of monotone AC-tree languages is not closed under complementation, and that the inclusion problem for monotone AC-tree automata is undecidable.
Document type :
Conference papers
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download
Contributor : Sophie Tison Connect in order to contact the contributor
Submitted on : Tuesday, November 16, 2010 - 5:31:58 PM
Last modification on : Monday, January 3, 2022 - 4:36:02 PM
Long-term archiving on: : Friday, October 26, 2012 - 3:45:45 PM


Files produced by the author(s)


  • HAL Id : inria-00536693, version 1



Hitoshi Ohsaki, Jean-Marc Talbot, Sophie Tison, Yves Roos. Monotone AC-Tree Automata. 12th International Conference on Logic for Programming Artificial Intelligence and Reasoning, 2005, Montego Bay, Jamaica. pp.337-351. ⟨inria-00536693⟩



Les métriques sont temporairement indisponibles