{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T01:39:41Z","timestamp":1779154781884,"version":"3.51.4"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,5,11]],"date-time":"2016-05-11T00:00:00Z","timestamp":1462924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Royal Society University Research Fellowship"},{"name":"Royal Society Research"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2016,5,25]]},"abstract":"<jats:p>\n            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\n            <jats:italic>finitely-generated<\/jats:italic>\n            weighted clones and\n            <jats:italic>finitely-generated<\/jats:italic>\n            weighted relational clones [SICOMP\u201913], and asked whether this connection holds in general. We answer this question in the affirmative for weighted (relational) clones with\n            <jats:italic>real<\/jats:italic>\n            weights and show that the complexity of the corresponding valued CSPs is preserved.\n          <\/jats:p>","DOI":"10.1145\/2898438","type":"journal-article","created":{"date-parts":[[2016,5,13]],"date-time":"2016-05-13T14:30:58Z","timestamp":1463149858000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["A Galois Connection for Weighted (Relational) Clones of Infinite Size"],"prefix":"10.1145","volume":"8","author":[{"given":"Peter","family":"Fulla","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,5,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556646"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/070708093"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070906"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press.   Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press.","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1018438.1021881"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970398.1970400"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380868"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/130906398"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2006.04.002"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_42"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1968.27.95"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2008.10.003"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Jean-Baptise Hiriart-Urruty and Claude Lemar\u00e9chal. 2001. Fundamentals of Convex Analysis. Springer Berlin.  Jean-Baptise Hiriart-Urruty and Claude Lemar\u00e9chal. 2001. Fundamentals of Convex Analysis. Springer Berlin.","DOI":"10.1007\/978-3-642-56468-0"},{"key":"e_1_2_1_18_1","first-page":"21","article-title":"The complexity of valued constraint satisfaction","volume":"113","author":"Jeavons Peter","year":"2014","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. (EATCS)"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/130945648"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450146"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_69"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_25_1","unstructured":"Johan Thapper. 2010. Aspects of a Constraint Optimisation Problem. Ph.D. Dissertation. Department of Computer Science and Information Science Link\u00f6ping University.  Johan Thapper. 2010. Aspects of a Constraint Optimisation Problem. Ph.D. Dissertation. Department of Computer Science and Information Science Link\u00f6ping University."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.25"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/140990346"},{"key":"e_1_2_1_28_1","unstructured":"Johan Thapper and Stanislav \u017divn\u00fd. 2015b. The complexity of finite-valued CSPs. J. ACM (2015). To appear.  Johan Thapper and Stanislav \u017divn\u00fd. 2015b. The complexity of finite-valued CSPs. J. ACM (2015). To appear."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Johan Thapper and Stanislav \u017divn\u00fd. 2015c. The power of Sherali-Adams relaxations for valued CSPs. (2015). Submitted for publication.  Johan Thapper and Stanislav \u017divn\u00fd. 2015c. The power of Sherali-Adams relaxations for valued CSPs. (2015). Submitted for publication.","DOI":"10.1007\/978-3-662-47672-7_86"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_86"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_68"},{"key":"e_1_2_1_32_1","unstructured":"Andrius Vaicenavi\u010dius. 2014. A Study of Weighted Clones. Master\u2019s thesis. Mathematical Institute University of Oxford.  Andrius Vaicenavi\u010dius. 2014. A Study of Weighted Clones. Master\u2019s thesis. Mathematical Institute University of Oxford."},{"key":"e_1_2_1_33_1","unstructured":"Ji\u0159\u00ed Van\u010dura. 2014. Weighted Clones. Master\u2019s thesis. Department of Algebra Charles University.  Ji\u0159\u00ed Van\u010dura. 2014. Weighted Clones. Master\u2019s thesis. Department of Algebra Charles University."},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Stanislav \u017divn\u00fd. 2012. The Complexity of Valued Constraint Satisfaction Problems. Springer.   Stanislav \u017divn\u00fd. 2012. The Complexity of Valued Constraint Satisfaction Problems. Springer.","DOI":"10.1007\/978-3-642-33974-5"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2898438","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2898438","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:56:30Z","timestamp":1750222590000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2898438"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,11]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,5,25]]}},"alternative-id":["10.1145\/2898438"],"URL":"https:\/\/doi.org\/10.1145\/2898438","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,11]]},"assertion":[{"value":"2015-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}