Querying constraints

摘要

The design of languages to tackle constraint satisfaction problems has a long history. Only more recently the reverse problem of introducing constraints as primitive constructs in programming languages has been addressed. A main task that the designers and implementers of such languages face is to use and adapt the concepts and algorithms from the extensive studies on constraints done in areas such as Mathematical Programming, Symbolic Computation, Artificial Intelligence, Program Verification and Computational Geometry. In this paper, we illustrate this task in a simple and yet important domain: linear arithmetic constraints. We show how one can design a querying system for sets of linear constraints by using basic concepts from logic programming and symbolic computation, as well as algorithms from linear programming and computational geometry. We conclude by reporting briefly on how notions of negation and canonical representation used in linear constraints can be generalized to account for cases in term algebras, symbolic computation, affine geometry, and elsewhere.