Please use this identifier to cite or link to this item:
Title: How to Determine the Expressive Power of Constraints
Authors: Jeavons, Peter
Cohen, David A.
Issue Date: 1999
Publisher: Springer
Source: Constraints, 4(2). p. 113-131
Abstract: Some constraint languages are more powerful than others because they allow us to express a larger collection of problems. In this paper, we give a precise meaning to this concept of expressive power for constraints over finite sets of values. The central result of the paper is that the expressive power of a given set of constraint types is determined by certain algebraic properties of the underlying relations. These algebraic properties can be calculated by solving a particular constraint satisfaction problem, which we call an ‘indicator problem’. We discuss the connection between expressive power and computational complexity, and show that indicator problems provide a simple method to test for tractability.
Document URI:
DOI: 10.1023/A:1009890709297
Type: Journal Contribution
Appears in Collections:Research publications

Show full item record


checked on Sep 2, 2020

Page view(s)

checked on May 25, 2022

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.