International Summer School on Constraints
in Computational Logic
Introduction to Constraint Solving
Jean-Pierre Jouannaud,
LRI, Université de Paris-Sud, France
Ralf Treinen
LRI, Université de Paris-Sud, France
The use of constraints in computational calculi allows to reconcile
declarative and operational aspects of computation. We see
constraint-based formalisms as a two-tiered architecture, consisting
of
- a constraint system and
- constrained language.
We will illustrate this approach with the examples of constraint
programming and constraint logic programming:
- The constraint system is a set of predicate-logic formulas together with
a fixed interpretation. The constraints have a purely
declarative semantics: a constraint describes a set of (tuples of)
values of its interpretation domain.
- The constrained language is a programming language together with an
operational semantics that uses constraints for control.
There are, however, operational aspects of the constraint system as
well as declarative aspects of the constrained language:
- The primarily declarative aspect of constraints has to be backed by a
concrete algorithm that efficiently provides the relevant semantical
information about constraints.
- The primarily operational semantics of the constraint language is
often used with a particular logical semantics in mind. The
operational semantics has to be correct with respect to this logical
semantics, and from constraint programming to automated deduction we
may encounter various demands to the completeness of the operational
semantics with regard to a logical semantics.
In this talk we will discuss the consequences of the two-tiered
architecture for the design of constraint systems.
ccl99@lri.fr
CCL'99 main page
Last change: April 7, 1999.