Feature Constraint Systems have been proposed as a logical data structure for constraint (logic) programming.
They provide a record-like view to trees by identifying subtrees by keyword
rather than by position. Their atomic constraints are finer grained than
in the constructor-based approach.
The recently proposed (see records for Logic Programming (92
version) in fact
generalizes the rational tree system of Prolog II.
which extends
by considering features as first class values.
As a consequence, contains constraints like
is a variable ranging over features,
while
We show that the satisfiability of conjunctions of atomic
-constraints
is NP-complete.
Satisfiability of quantifier-free -constraints is shown to be
decidable,
while the
fragment of the
first order theory is undecidable.