School Homepage

An Interval Constraint System for Lattice Domains

Antonio J. Fernandez
E.T.S. de Ingenieria Informatica
Departamento de Lenguajes y Ciencias de la Computacion
Despacho 3.2.50
Universidad de Malaga
Teatinos s/n
29071-Malaga
Spain

Patricia M. Hill
School of Computing
The University of Leeds
Leeds LS2 9JT
England

Abstract:

We present a generic framework for defining and solving interval constraints on any set of domains (finite or infinite) that are lattices. The approach is based on the use of a single form of constraint similar to that of an indexical used by CLP for finite domains and on a particular generic definition of an interval domain built from an arbitrary lattice. We provide the theoretical foundations for this framework and a schematic procedure for the operational semantics. Examples are provided that illustrate how new (compound) constraint solvers can be constructed from existing solvers using lattice combinators and how different solvers (possibly on distinct domains) can communicate and hence, cooperate in solving a problem. We describe the language clpl which is a prototype implementation of this framework and discuss ways in which this implementation may be improved.