A Galois connection for weighted (relational) clones of infinite size
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-gener...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Association for Computing Machinery
2015
|
| _version_ | 1797090304101187584 |
|---|---|
| author | Fulla, P Zivny, S |
| author_facet | Fulla, P Zivny, S |
| author_sort | Fulla, P |
| collection | OXFORD |
| description | 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 (relational) clones with real weights and show that the complexity of the corresponding valued CSPs is preserved. |
| first_indexed | 2024-03-07T03:16:37Z |
| format | Journal article |
| id | oxford-uuid:b60091b1-1645-46aa-b478-0dde98837004 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T03:16:37Z |
| publishDate | 2015 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:b60091b1-1645-46aa-b478-0dde988370042022-03-27T04:37:49ZA Galois connection for weighted (relational) clones of infinite sizeJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:b60091b1-1645-46aa-b478-0dde98837004Symplectic Elements at OxfordAssociation for Computing Machinery2015Fulla, PZivny, SA 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 (relational) clones with real weights and show that the complexity of the corresponding valued CSPs is preserved. |
| spellingShingle | Fulla, P Zivny, S A Galois connection for weighted (relational) clones of infinite size |
| title | A Galois connection for weighted (relational) clones of infinite size |
| title_full | A Galois connection for weighted (relational) clones of infinite size |
| title_fullStr | A Galois connection for weighted (relational) clones of infinite size |
| title_full_unstemmed | A Galois connection for weighted (relational) clones of infinite size |
| title_short | A Galois connection for weighted (relational) clones of infinite size |
| title_sort | galois connection for weighted relational clones of infinite size |
| work_keys_str_mv | AT fullap agaloisconnectionforweightedrelationalclonesofinfinitesize AT zivnys agaloisconnectionforweightedrelationalclonesofinfinitesize AT fullap galoisconnectionforweightedrelationalclonesofinfinitesize AT zivnys galoisconnectionforweightedrelationalclonesofinfinitesize |