Ordering Constraints over Feature Trees

Abstract : Feature trees are the formal basis for algorithms manipulating record like structures in constraint programming, computational linguistics and in concrete applications like software configuration management. Feature trees model records, and constraints over feature trees yield extensible and modular record descriptions. We introduce the constraint system FT< of ordering constraints interpreted over feature trees. Under the view that feature trees represent symbolic information, the relation < corresponds to the information ordering (``carries less information than''). We present two algorithms in cubic time, one for the satisfiability problem and one for the entailment problem of FT<. We show that FT< has the independence property. We are thus able to handle negative conjuncts via entailment and obtain a cubic algorithm that decides the satisfiability of conjunctions of positive and negated ordering constraints over feature trees. Furthermore, we reduce the satisfiability problem of D{"o}rre's weak subsumption constraints to the satisfiability problem of FT< and improve the complexity bound for solving weak subsumption constraints from O(n^5) to O(n^3).
Type de document :
Article dans une revue
Constraints, an International Journal, Elsevier, 2000, 5 (1--2), pp.7--42
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00536799
Contributeur : Joachim Niehren <>
Soumis le : dimanche 6 février 2011 - 21:33:22
Dernière modification le : lundi 20 novembre 2017 - 15:14:01
Document(s) archivé(s) le : samedi 7 mai 2011 - 02:16:16

Fichier

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

Identifiants

  • HAL Id : inria-00536799, version 1

Citation

Martin Müller, Joachim Niehren, Andreas Podelski. Ordering Constraints over Feature Trees. Constraints, an International Journal, Elsevier, 2000, 5 (1--2), pp.7--42. 〈inria-00536799〉

Partager

Métriques

Consultations de la notice

91

Téléchargements de fichiers

78