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.
Type de document :
Communication dans un congrès
Geoff Sutcliffe and Andrei Voronkov. 12th International Conference on Logic for Programming Artificial Intelligence and Reasoning, 2005, Montego Bay, Jamaica. Springer, 3835, pp.337-351, 2005, Lecture Notes in Computer Science
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00536693
Contributeur : Sophie Tison <>
Soumis le : mardi 16 novembre 2010 - 17:31:58
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : vendredi 26 octobre 2012 - 15:45:45

Fichier

Monotone-AC-Tree-Automata.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00536693, version 1

Collections

Citation

Hitoshi Ohsaki, Jean-Marc Talbot, Sophie Tison, Yves Roos. Monotone AC-Tree Automata. Geoff Sutcliffe and Andrei Voronkov. 12th International Conference on Logic for Programming Artificial Intelligence and Reasoning, 2005, Montego Bay, Jamaica. Springer, 3835, pp.337-351, 2005, Lecture Notes in Computer Science. 〈inria-00536693〉

Partager

Métriques

Consultations de la notice

218

Téléchargements de fichiers

176