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)

6
checked on May 25, 2022

Google ScholarTM

Check

Altmetric


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