Skip to main content

Constructing constraints

P.G.Jeavons

Abstract

It is well-known that there is a trade-off between the expressive power of a constraint language and the tractability of the problems it can express. But how can you determine the expressive power of a given constraint language, and how can you tell if problems expressed in that language are tractable? In this paper we discuss some general approaches to these questions We show that for languages over a finite domain the concept of an �indicator Problem� gives a universal construction for any constraint within the expressive power of a language. We also discuss the fact that all known tractable languages over finite domains are characterised by the presence of a particular solution to a corresponding indicator problem, and raise the question of whether this is a universal property of tractable languages

Book Title
Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming (CP98)
Pages
2−16
Series
Lecture Notes in Computer Science
Volume
1520
Year
1998