# Publication details

##
A Feature-based Constraint System for Logic Programming with Entailment

Hassan Aït-Kaci, Andreas Podelski, Gert Smolka

Theoretical Computer Science 122(1--2):263-283, January 1994

This paper presents the constraint system FT, which we feel is an intriguing alternative to Herbrand both theoretically and
practically. As does Herbrand, FT provides a universal data
structure based on trees. However, the trees of FT (called
feature trees) are more general than the trees of Herbrand
(called constructor trees), and the constraints of FT are finer
grained and of different expressivity. The basic notion of FT
are functional attributes called features, which provide for
record-like descriptions of data avoiding the overspecification
intrinsic in Herbrand's constructor-based descriptions.
The feature tree structure fixes an algebraic semantics for FT.
We will also establish a logical semantics, which is given by
three axiom schemes fixing the first-order theory FT.
FT is a constraint system for logic programming, providing a test
for unsatisfiability, and a test for entailment between
constraints, which is needed for advanced control mechanisms.
The two major technical contributions of this paper are (1) an
incremental entailment simplification system that is proved to be
sound and complete, and (2) a proof showing that FT satisfies the
so-called ``independence of negative constraints''.

Download PDF
Show BibTeX

@ARTICLE{RR-92-17,
title = {A Feature-based Constraint System for Logic Programming with Entailment},
author = {Hassan A{\"\i}t-Kaci and Andreas Podelski and Gert Smolka},
year = {1994},
month = {jan},
journal = {{Theoretical Computer Science}},
volume = {122},
pages = {"263--283"},
number = {"1--2"},
}

Login to edit

Webmaster,
Wed Sep 16 10:47:00 2009