The expressive power of valued constraints: Hierarchies and collapses

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...

Полное описание

Библиографические подробности
Главные авторы: Cohen, D, Jeavons, P, Živný, S
Формат: Journal article
Язык:English
Опубликовано: Elsevier 2008
_version_ 1826297864165261312
author Cohen, D
Jeavons, P
Živný, S
author_facet Cohen, D
Jeavons, P
Živný, S
author_sort Cohen, D
collection OXFORD
description 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.
first_indexed 2024-03-07T04:38:07Z
format Journal article
id oxford-uuid:d0ad4ee4-b42e-4144-a8e3-c6de99a7d677
institution University of Oxford
language English
last_indexed 2024-03-07T04:38:07Z
publishDate 2008
publisher Elsevier
record_format dspace
spelling oxford-uuid:d0ad4ee4-b42e-4144-a8e3-c6de99a7d6772022-03-27T07:51:39ZThe expressive power of valued constraints: Hierarchies and collapsesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:d0ad4ee4-b42e-4144-a8e3-c6de99a7d677EnglishSymplectic Elements at OxfordElsevier2008Cohen, DJeavons, PŽivný, SIn 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.
spellingShingle Cohen, D
Jeavons, P
Živný, S
The expressive power of valued constraints: Hierarchies and collapses
title The expressive power of valued constraints: Hierarchies and collapses
title_full The expressive power of valued constraints: Hierarchies and collapses
title_fullStr The expressive power of valued constraints: Hierarchies and collapses
title_full_unstemmed The expressive power of valued constraints: Hierarchies and collapses
title_short The expressive power of valued constraints: Hierarchies and collapses
title_sort expressive power of valued constraints hierarchies and collapses
work_keys_str_mv AT cohend theexpressivepowerofvaluedconstraintshierarchiesandcollapses
AT jeavonsp theexpressivepowerofvaluedconstraintshierarchiesandcollapses
AT zivnys theexpressivepowerofvaluedconstraintshierarchiesandcollapses
AT cohend expressivepowerofvaluedconstraintshierarchiesandcollapses
AT jeavonsp expressivepowerofvaluedconstraintshierarchiesandcollapses
AT zivnys expressivepowerofvaluedconstraintshierarchiesandcollapses