{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:14:46Z","timestamp":1760202886404,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,10,14]],"date-time":"2014-10-14T00:00:00Z","timestamp":1413244800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001824","name":"Grant Agency of the Czech Republic","doi-asserted-by":"crossref","award":["GACR 13-01832S"],"award-info":[{"award-number":["GACR 13-01832S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM SIGLOG News"],"published-print":{"date-parts":[[2014,10,14]]},"abstract":"<jats:p>This column gives a brief survey of current research on the complexity of the constraint satisfaction problem (CSP) over fixed constraint languages.<\/jats:p>","DOI":"10.1145\/2677161.2677165","type":"journal-article","created":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T19:06:00Z","timestamp":1585940760000},"page":"14-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Constraint satisfaction problem and universal algebra"],"prefix":"10.1145","volume":"1","author":[{"given":"Libor","family":"Barto","sequence":"first","affiliation":[{"name":"Charles University in Prague"}]}],"member":"320","published-online":{"date-parts":[[2014,10,14]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1017\/CBO9780511804090"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1109\/LICS.2011.25"},{"doi-asserted-by":"crossref","unstructured":"Libor Barto. 2014. The Collapse of the Bounded Width Hierarchy. (2014). manuscript. Libor Barto. 2014. The Collapse of the Bounded Width Hierarchy. (2014). manuscript.","key":"e_1_2_1_3_1","DOI":"10.1093\/logcom\/exu070"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1137\/080743238"},{"doi-asserted-by":"crossref","unstructured":"Libor Barto and Marcin Kozik. 2012a. Absorbing Subalgebras Cyclic Terms and the Constraint Satisfaction Problem. Logical Methods in Computer Science 8 1 (2012). Libor Barto and Marcin Kozik. 2012a. Absorbing Subalgebras Cyclic Terms and the Constraint Satisfaction Problem. Logical Methods in Computer Science 8 1 (2012).","key":"e_1_2_1_5_1","DOI":"10.2168\/LMCS-8(1:7)2012"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1145\/2213977.2214061"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1145\/2556646"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1137\/070708093"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1090\/S0002-9947-09-04874-0"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1017\/S0305004100013463"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1007\/978-3-540-92800-3_8"},{"key":"e_1_2_1_12_1","first-page":"1","article-title":"Galois theory for Post algebras","volume":"3","author":"Bodnar\u010duk V. G.","year":"1969","journal-title":"I, II. Kibernetika (Kiev)"},{"unstructured":"Andrei Bulatov. 2009. Bounded relational width. (2009). manuscript. Andrei Bulatov. 2009. Bounded relational width. (2009). manuscript.","key":"e_1_2_1_13_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1137\/050628957"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1137\/S0097539700376676"},{"unstructured":"Andrei A. Bulatov. 2002. Mal'tsev constraints are tractable. Electronic Colloquium on Computational Complexity (ECCC) 034 (2002). Andrei A. Bulatov. 2002. Mal'tsev constraints are tractable. Electronic Colloquium on Computational Complexity (ECCC) 034 (2002).","key":"e_1_2_1_16_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1016\/j.jalgebra.2004.07.044"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1145\/1970398.1970400"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1145\/2528400"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1007\/978-3-540-92800-3_5"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1145\/2213977.2214059"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1007\/s00012-009-2113-5"},{"key":"e_1_2_1_23_1","volume-title":"Lecture Notes in Computer Science","volume":"7230","author":"Chen Hubie","year":"2012"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1137\/130906398"},{"doi-asserted-by":"crossref","unstructured":"V\u00edctor Dalmau. 2006. Generalized majority-minority operations are tractable. Log. Methods Comput. Sci. 2 4 (2006) 4:1 14. V\u00edctor Dalmau. 2006. Generalized majority-minority operations are tractable. Log. Methods Comput. Sci . 2 4 (2006) 4:1 14.","key":"e_1_2_1_25_1","DOI":"10.2168\/LMCS-2(4:1)2006"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1137\/100811258"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1137\/S0097539794266766"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.2140\/pjm.1968.27.95"},{"volume-title":"Surveys in combinatorics","year":"2007","author":"H\u00e5stad Johan","key":"e_1_2_1_29_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_2_1_31_1","volume-title":"Contemporary Mathematics","volume":"76","author":"Hobby David","year":"1988"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1109\/LICS.2007.50"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1137\/0217058"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1016\/S0304-3975(97)00230-2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1145\/263867.263489"},{"doi-asserted-by":"crossref","unstructured":"Emil Kiss and Matthew Valeriote. 2007. On tractability and congruence distributivity. Log. Methods Comput. Sci. 3 2 (2007) 2:6 20 pp. (electronic). Emil Kiss and Matthew Valeriote. 2007. On tractability and congruence distributivity. Log. Methods Comput. Sci . 3 2 (2007) 2:6 20 pp. (electronic).","key":"e_1_2_1_36_1","DOI":"10.2168\/LMCS-3(2:6)2007"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1145\/1536414.1536512"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1145\/321864.321877"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1016\/j.tcs.2008.12.048"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1007\/s00012-007-2012-6"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1109\/LICS.2011.27"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1007\/s00012-008-2122-9"},{"unstructured":"Christos H. Papadimitriou. 1994. Computational complexity. Addison-Wesley Publishing Company Reading MA. xvi+523 pages. Christos H. Papadimitriou. 1994. Computational complexity . Addison-Wesley Publishing Company Reading MA. xvi+523 pages.","key":"e_1_2_1_43_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_44_1","DOI":"10.1145\/1374376.1374414"},{"doi-asserted-by":"publisher","key":"e_1_2_1_45_1","DOI":"10.1145\/1391289.1391291"},{"unstructured":"Francesca Rossi Peter van Beek and Toby Walsh. 2006. Handbook of Constraint Programming (Foundations of Artificial Intelligence). Elsevier Science Inc. New York NY USA. Francesca Rossi Peter van Beek and Toby Walsh. 2006. Handbook of Constraint Programming (Foundations of Artificial Intelligence) . Elsevier Science Inc. New York NY USA.","key":"e_1_2_1_46_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_47_1","DOI":"10.1145\/800133.804350"},{"doi-asserted-by":"crossref","unstructured":"Mark H. Siggers. 2010. A strong Malcev condition for locally finite varieties omitting the unary type. Algebra universalis 64 1-2 (2010) 15--20. Mark H. Siggers. 2010. A strong Malcev condition for locally finite varieties omitting the unary type. Algebra universalis 64 1-2 (2010) 15--20.","key":"e_1_2_1_48_1","DOI":"10.1007\/s00012-010-0082-3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_49_1","DOI":"10.1007\/BF00299636"},{"doi-asserted-by":"publisher","key":"e_1_2_1_50_1","DOI":"10.4153\/CJM-1977-054-9"},{"doi-asserted-by":"crossref","unstructured":"Stanislav \u017divn\u00fd. 2012. The complexity of valued constraint satisfaction problems. Springer Heidelberg. xviii+170 pages. Stanislav \u017divn\u00fd. 2012. The complexity of valued constraint satisfaction problems . Springer Heidelberg. xviii+170 pages.","key":"e_1_2_1_51_1","DOI":"10.1007\/978-3-642-33974-5"}],"container-title":["ACM SIGLOG News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2677161.2677165","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2677161.2677165","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:11:56Z","timestamp":1750227116000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2677161.2677165"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,14]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,10,14]]}},"alternative-id":["10.1145\/2677161.2677165"],"URL":"https:\/\/doi.org\/10.1145\/2677161.2677165","relation":{},"ISSN":["2372-3491"],"issn-type":[{"type":"electronic","value":"2372-3491"}],"subject":[],"published":{"date-parts":[[2014,10,14]]},"assertion":[{"value":"2014-10-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}