{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T21:13:46Z","timestamp":1772313226621,"version":"3.50.1"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"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":["201\/09\/P223"],"award-info":[{"award-number":["201\/09\/P223"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001823","name":"Ministry of Education, Youth and Sports","doi-asserted-by":"publisher","award":["MSM 0021620839"],"award-info":[{"award-number":["MSM 0021620839"]}],"id":[{"id":"10.13039\/501100001823","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["DEC-2011\/01\/B\/ST6\/01006"],"award-info":[{"award-number":["DEC-2011\/01\/B\/ST6\/01006"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>We prove that constraint satisfaction problems without the ability to count are solvable by the local consistency checking algorithm. This settles three (equivalent) conjectures: Feder--Vardi [SICOMP\u201998], Bulatov [LICS\u201904] and Larose--Z\u00e1dori [AU\u201907].<\/jats:p>","DOI":"10.1145\/2556646","type":"journal-article","created":{"date-parts":[[2014,2,4]],"date-time":"2014-02-04T14:16:21Z","timestamp":1391523381000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":103,"title":["Constraint Satisfaction Problems Solvable by Local Consistency Methods"],"prefix":"10.1145","volume":"61","author":[{"given":"Libor","family":"Barto","sequence":"first","affiliation":[{"name":"McMaster University and Charles University in Prague"}]},{"given":"Marcin","family":"Kozik","sequence":"additional","affiliation":[{"name":"Jagiellonian University"}]}],"member":"320","published-online":{"date-parts":[[2014,1]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Libor Barto. 2013. The collapse of the bounded width hierarchy. In preparation."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/080743238"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.32"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.34"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214061"},{"key":"e_1_2_1_6_1","unstructured":"Libor Barto Marcin Kozik and David Stanovsk\u00fd. 2013. Mal\u2019tsev conditions lack of absorption and solvability. Submitted."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781439851302"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-09-04874-0"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100013463"},{"key":"e_1_2_1_10_1","first-page":"1","article-title":"Galois theory for Post algebras","volume":"3","author":"Bodnar\u010duk V. G.","year":"1969","unstructured":"V. G. Bodnar\u010duk, L. A. Kalu\u017enin, V. N. Kotov, and B. A. Romov. 1969. Galois theory for Post algebras. I, II. Kibernetika (Kiev) 3, 1--10; ibid. 1969, no. 5, 1--9.","journal-title":"I, II. Kibernetika (Kiev)"},{"key":"e_1_2_1_11_1","unstructured":"Andrei Bulatov. 2006a. Complexity of Maltsev constraints. Algebra i Logika 26 1 (In Russian)."},{"key":"e_1_2_1_12_1","unstructured":"Andrei Bulatov. 2009. Bounded relational width. Manuscript. http:\/\/www.cs.sfu.ca\/~abulatov\/papers\/relwidth.pdf."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/050628957"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/788023.789067"},{"key":"e_1_2_1_16_1","first-page":"583","article-title":"Complexity of the conservative generalized satisfiability problem","volume":"397","author":"Bulatov A. A.","year":"2004","unstructured":"A. A. Bulatov. 2004a. Complexity of the conservative generalized satisfiability problem. Dokl. Akad. Nauk 397, 5, 583--585.","journal-title":"Dokl. Akad. Nauk"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1018438.1021881"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2004.07.044"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_4"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/646253.683938"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_5"},{"key":"e_1_2_1_23_1","volume-title":"Graduate Texts in Mathematics","volume":"78","author":"Burris Stanley N.","unstructured":"Stanley N. Burris and H. P. Sankappanavar. 1981. A Course in Universal Algebra. Graduate Texts in Mathematics, Vol. 78, Springer-Verlag, New York."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-009-2113-5"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1968.27.95"},{"key":"e_1_2_1_27_1","volume-title":"The Structure of Finite Algebras. Contemporary Mathematics","author":"Hobby David","unstructured":"David Hobby and Ralph McKenzie. 1988. The Structure of Finite Algebras. Contemporary Mathematics, Vol. 76, American Mathematical Society, Providence, RI."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.50"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Emil Kiss and Matthew Valeriote. 2007. On tractability and congruence distributivity. Log. Meth. Comput. Sci. 3 2 2:6 (electronic).","DOI":"10.2168\/LMCS-3(2:6)2007"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.048"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-007-2012-6"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1142\/S021819670900524X"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-008-2122-9"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2556646","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2556646","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:05Z","timestamp":1750234205000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2556646"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1145\/2556646"],"URL":"https:\/\/doi.org\/10.1145\/2556646","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]},"assertion":[{"value":"2012-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-11-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}