Publication details

Saarland University Computer Science

Feature Constraints with First-Class Features

Ralf Treinen

Mathematical Foundations of Computer Science, pp. 734--743, Springer-Verlag, 1993

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 forallëxists fragment of the first order theory is undecidable.

Download PDF        Show BibTeX               


Login to edit


Webmaster, Wed Sep 16 10:47:00 2009