{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T21:31:22Z","timestamp":1743024682453,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_42","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"517-528","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A Galois Connection for Valued Constraint Languages of Infinite Size"],"prefix":"10.1007","author":[{"given":"Peter","family":"Fulla","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"42_CR1","doi-asserted-by":"crossref","unstructured":"Barto, L., Kozik, M.: Constraint Satisfaction Problems Solvable by Local Consistency Methods. Journal of the ACM 61(1), article No. 3","DOI":"10.1145\/2556646"},{"issue":"5","key":"42_CR2","doi-asserted-by":"publisher","first-page":"1782","DOI":"10.1137\/070708093","volume":"38","author":"L Barto","year":"2009","unstructured":"Barto, L., Kozik, M., Niven, T.: The CSP dichotomy holds for digraphs with no sources and no sinks. SIAM Journal on Computing 38(5), 1782\u20131802 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"42_CR3","doi-asserted-by":"crossref","unstructured":"Boyd, S.P., Vandenberghe, L.: Convex Optimization, CUP (2004)","DOI":"10.1017\/CBO9780511804441"},{"key":"42_CR4","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: A graph of a relational structure and constraint satisfaction problems. In: Proc. LICS 2004. IEEE Computer Society, pp. 448\u2013457 (2004)","DOI":"10.1109\/LICS.2004.1319639"},{"issue":"1","key":"42_CR5","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"A Bulatov","year":"2006","unstructured":"Bulatov, A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. Journal of the ACM 53(1), 66\u2013120 (2006)","journal-title":"Journal of the ACM"},{"issue":"3","key":"42_CR6","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A Bulatov","year":"2005","unstructured":"Bulatov, A., Krokhin, A., Jeavons, P.: Classifying the Complexity of Constraints using Finite Algebras. SIAM Journal on Computing 34(3), 720\u2013742 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"42_CR7","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: Complexity of conservative constraint satisfaction problems. ACM Transactions on Computational Logic 12(4), article 24","DOI":"10.1145\/1970398.1970400"},{"key":"42_CR8","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A., Krokhin, A.A., Jeavons, P.G.: The complexity of maximal constraint languages. In: Proc. STOC 2001, pp. 667\u2013674 (2001)","DOI":"10.1145\/380752.380868"},{"issue":"5","key":"42_CR9","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1137\/130906398","volume":"42","author":"DA Cohen","year":"2013","unstructured":"Cohen, D.A., Cooper, M.C., Creed, P., Jeavons, P., \u017divn\u00fd, S.: An algebraic theory of complexity for discrete optimisation. SIAM Journal on Computing 42(5), 915\u20131939 (2013)","journal-title":"SIAM Journal on Computing"},{"issue":"11","key":"42_CR10","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1016\/j.artint.2006.04.002","volume":"170","author":"DA Cohen","year":"2006","unstructured":"Cohen, D.A., Cooper, M.C., Jeavons, P.G., Krokhin, A.A.: The Complexity of Soft Constraint Satisfaction. Artificial Intelligence 170(11), 983\u20131016 (2006)","journal-title":"Artificial Intelligence"},{"issue":"1","key":"42_CR11","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM Journal on Computing 28(1), 57\u2013104 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"42_CR12","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the Complexity of $${H}$$-coloring. Journal of Combinatorial Theory, Series B 48(1), 92\u2013110 (1990)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"3","key":"42_CR13","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.cosrev.2008.10.003","volume":"2","author":"P Hell","year":"2008","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Colouring, constraint satisfaction, and complexity. Computer Science Review 2(3), 143\u2013163 (2008)","journal-title":"Computer Science Review"},{"key":"42_CR14","first-page":"21","volume":"113","author":"P Jeavons","year":"2014","unstructured":"Jeavons, P., Krokhin, A., \u017divn\u00fd, S.: The complexity of valued constraint satisfaction. Bulletin of the European Association for Theoretical Computer Science (EATCS) 113, 21\u201355 (2014)","journal-title":"Bulletin of the European Association for Theoretical Computer Science (EATCS)"},{"issue":"4","key":"42_CR15","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"PG Jeavons","year":"1997","unstructured":"Jeavons, P.G., Cohen, D.A., Gyssens, M.: Closure Properties of Constraints. Journal of the ACM 44(4), 527\u2013548 (1997)","journal-title":"Journal of the ACM"},{"issue":"1","key":"42_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/130945648","volume":"44","author":"V Kolmogorov","year":"2015","unstructured":"Kolmogorov, V., Thapper, J., \u017divn\u00fd, S.: The power of linear programming for general-valued CSPs. SIAM Journal on Computing 44(1), 1\u201336 (2015)","journal-title":"SIAM Journal on Computing"},{"key":"42_CR17","doi-asserted-by":"crossref","unstructured":"Kolmogorov, V., \u017divn\u00fd, S.: The complexity of conservative valued CSPs. Journal of the ACM 60(2), article No. 10","DOI":"10.1145\/2450142.2450146"},{"key":"42_CR18","doi-asserted-by":"crossref","unstructured":"Kozik, M., Ochremiak, J.: Algebraic properties of valued constraintsatisfaction problem. In: Proc. ICALP 2015. Springer (2015)","DOI":"10.1007\/978-3-662-47672-7_69"},{"key":"42_CR19","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proc. STOC 1978, pp. 216\u2013226. ACM (1978)","DOI":"10.1145\/800133.804350"},{"key":"42_CR20","unstructured":"Thapper, J.: Aspects of a constraint optimisation problem, Ph.D. thesis, Department of Computer Science and Information Science, Link\u00f6ping University (2010)"},{"key":"42_CR21","doi-asserted-by":"crossref","unstructured":"Thapper, J., \u017divn\u00fd, S.: The power of linear programming for valued CSPs. In: Proc. FOCS 2012, pp. 669\u2013678. IEEE (2012)","DOI":"10.1109\/FOCS.2012.25"},{"key":"42_CR22","doi-asserted-by":"crossref","unstructured":"Thapper, J., \u017divn\u00fd, S.: The complexity of finite-valued CSPs. In: Proc. STOC 2013, pp. 695\u2013704. ACM (2013)","DOI":"10.1145\/2488608.2488697"},{"key":"42_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1007\/978-3-642-39206-1_68","volume-title":"Automata, Languages, and Programming","author":"H Uppman","year":"2013","unstructured":"Uppman, H.: The complexity of three-element min-sol and conservative min-cost-hom. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 804\u2013815. Springer, Heidelberg (2013)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T12:56:38Z","timestamp":1675860998000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}