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.
Download PDF Show BibTeX
Login to edit