Ordering Constraints over Feature Trees

Abstract : Feature trees have been used to accommodate records in constraint programming and record like structures in computational linguistics. Feature trees model records, and feature constraints 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 a polynomial algorithm that decides the satisfiability of conjunctions of positive and negative information ordering constraints over feature trees. Our results include algorithms for the satisfiability problem and the entailment problem of FT< in time O(n^3). We also show that FT< has the independence property and are thus able to handle negative conjuncts via entailment. Furthermore, we reduce the satisfiability problem of Dörre's weak-subsumption constraints to the satisfiability problem of FT<. This improves the complexity bound for solving weak subsumption constraints from O(n^5) to O(n^3). A journal extension is available at http://hal.inria.fr/docs/00/53/67/99/PDF/o.pdf
Type de document :
Communication dans un congrès
Gert Smolka. 3rd International Conference on Principles and Practice of Constraint Programming, 1997, Schloss Hagenberg, Linz, Austria. Springer, 1330, pp.297--311, 1997, Lecture Notes on Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00536815
Contributeur : Joachim Niehren <>
Soumis le : mardi 16 novembre 2010 - 23:09:57
Dernière modification le : lundi 20 novembre 2017 - 15:14:01

Identifiants

  • HAL Id : inria-00536815, version 1

Citation

Martin Müller, Joachim Niehren, Andreas Podelski. Ordering Constraints over Feature Trees. Gert Smolka. 3rd International Conference on Principles and Practice of Constraint Programming, 1997, Schloss Hagenberg, Linz, Austria. Springer, 1330, pp.297--311, 1997, Lecture Notes on Computer Science. 〈inria-00536815〉

Partager

Métriques

Consultations de la notice

21