Publication details

Saarland University Computer Science

Ordering Constraints over Feature Trees

Martin Müller, Joachim Niehren, Andreas Podelski

Proceedings of the Third International Conference on Principles and Practice of Constraint Programming, Vol. 1330 of Lecture Notes in Computer Science, pp. 297--311, Springer-Verlag, 1997

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)$.

Download PDF        Show BibTeX               


Login to edit


Webmaster, Wed Sep 16 10:47:00 2009