Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/730
Title: | How to Determine the Expressive Power of Constraints | Authors: | Jeavons, Peter Cohen, David A. GYSSENS, Marc |
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: | http://hdl.handle.net/1942/730 | DOI: | 10.1023/A:1009890709297 | Type: | Journal Contribution |
Appears in Collections: | Research publications |
Show full item record
SCOPUSTM
Citations
30
checked on Sep 2, 2020
Page view(s)
36
checked on Nov 7, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.