Ordering Constraints over Feature Trees
Author: Martin Müller and Joachim Niehren and Andreas
Podelski
Editor: Gert Smolka
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)$.
|