Journal article icon

Journal article

A Galois connection for weighted (relational) clones 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 for weighted (rela...

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

Actions


Access Document


Files:
Publisher copy:
10.1145/2898438

Authors


More by this author
Institution:
University of Oxford
Oxford college:
Balliol College
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Royal Society More from this funder
Publisher:
Association for Computing Machinery Publisher's website
Journal:
ACM Transactions on Computation Theory Journal website
Volume:
8
Issue:
3
Article number:
9
Publication date:
2015-01-01
DOI:
EISSN:
1942-3462
ISSN:
1942-3454
Source identifiers:
576229
Keywords:
Pubs id:
pubs:576229
UUID:
uuid:b60091b1-1645-46aa-b478-0dde98837004
Local pid:
pubs:576229
Deposit date:
2015-11-27

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