Ordering Constraints over Feature Trees Expressed in Second-order Monadic Logic

Abstract : The system FT< of ordering constraints over feature trees has been introduced as an extension of the system FT of equality constraints over feature trees. We investigate decidability and complexity questions for fragments of the first-order theory of FT<. It is well-known that the first-order theory of FT< is decidable and that several of its fragments can be decided in quasi-linear time, including the satisfiability problem of FT< and its entailment problem with existential quantification p |= models E x1 ... E xn p' Much less is known on the first-order theory of FT<. The satisfiability problem of FT< can be decided in cubic time, as well as its entailment problem without existential quantification. Our main result is that the entailment problem of FT< with existential quantifiers is decidable but PSPACE-hard. Our decidability proof is based on a new technique where feature constraints are expressed in second-order monadic logic with countably many successors SwS. We thereby reduce the entailment problem of FT< with existential quantification to Rabin's famous theorem on tree automata.
Type de document :
Communication dans un congrès
Tobias Nipkow. 9th International Conference on Rewriting Techniques and Applications, 1998, Tsukuba, Japan. Springer, 1379, pp.196--210, 1998, Lecture Notes on Computer Science
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00536814
Contributeur : Joachim Niehren <>
Soumis le : mardi 16 novembre 2010 - 23:09:54
Dernière modification le : mardi 31 octobre 2017 - 14:22:18
Document(s) archivé(s) le : jeudi 17 février 2011 - 03:15:58

Fichiers

SWSJournal99.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00536814, version 1

Citation

Martin Müller, Joachim Niehren. Ordering Constraints over Feature Trees Expressed in Second-order Monadic Logic. Tobias Nipkow. 9th International Conference on Rewriting Techniques and Applications, 1998, Tsukuba, Japan. Springer, 1379, pp.196--210, 1998, Lecture Notes on Computer Science. 〈inria-00536814〉

Partager

Métriques

Consultations de la notice

54

Téléchargements de fichiers

64