Journal article
The expressive power of valued constraints: Hierarchies and collapses
- Abstract:
- In this paper, we investigate the ways in which a fixed collection of valued constraints can be combined to express other valued constraints. We show that in some cases, a large class of valued constraints, of all possible arities, can be expressed by using valued constraints over the same domain of a fixed finite arity. We also show that some simple classes of valued constraints, including the set of all monotonic valued constraints with finite cost values, cannot be expressed by a subset of any fixed finite arity, and hence form an infinite hierarchy.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 1.4MB, Terms of use)
-
- Publisher copy:
- 10.1016/j.tcs.2008.08.036
Authors
+ Engineering and Physical Sciences Research Council
More from this funder
- Funding agency for:
- Živný, S
- Grant:
- EP/F01161X/1
- Publisher:
- Elsevier
- Journal:
- Theoretical Computer Science More from this journal
- Volume:
- 409
- Issue:
- 1
- Pages:
- 137-153
- Publication date:
- 2008-12-06
- DOI:
- ISSN:
-
0304-3975
- Language:
-
English
- Keywords:
- Pubs id:
-
292950
- UUID:
-
uuid:d0ad4ee4-b42e-4144-a8e3-c6de99a7d677
- Local pid:
-
pubs:292950
- Source identifiers:
-
292950
- Deposit date:
-
2013-02-20
- ARK identifier:
Terms of use
- Copyright holder:
- Elsevier BV
- Copyright date:
- 2008
- Notes:
- Copyright 2008 Elsevier B.V. All rights reserved. Re-use of this article is permitted in accordance with the Terms and Conditions set out at http://www.elsevier.com/open-access/userlicense/1.0/
If you are the owner of this record, you can report an update to it here: Report update to this record