Document Server@UHasselt >
Research >
Research publications >
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 |
Citation: | 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. |
URI: | http://hdl.handle.net/1942/730 |
DOI: | 10.1023/A:1009890709297 |
ISSN: | 1383-7133 |
Type: | Journal Contribution |
Appears in Collections: | Research publications
|
Files in This Item:
There are no files associated with this item.
|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
|