Conference item icon

Conference item

A Galois connection for valued constraint languages of infinite size

Abstract:

A Galois connection between clones and relational clones on a fixed finite domain is one of the cornerstones of the so-called algebraic approach to the computational complexity of non-uniform Constraint Satisfaction Problems (CSPs). Cohen et al. established a Galois connection between finitely-generated weighted clones and finitely-generated weighted relational clones [SICOMP’13], and asked whether this connection holds in general. We answer this question in the affirmative ...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More from this funder
Funding agency for:
Živný, S
Royal Society More from this funder
Publisher:
Springer Berlin Heidelberg Publisher's website
DOI:
ISSN:
0302-9743
ISBN:
9783662476727
Language:
English
UUID:
uuid:6c9a8d14-dfe1-4ca0-aa5e-6d09e14af3ba
Local pid:
ora:11363
Deposit date:
2015-05-06

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP