{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:11:51Z","timestamp":1761621111392,"version":"3.41.2"},"reference-count":28,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2012,2,20]],"date-time":"2012-02-20T00:00:00Z","timestamp":1329696000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>The Algebraic Dichotomy Conjecture states that the Constraint Satisfaction Problem over a fixed template is solvable in polynomial time if the algebra of polymorphisms associated to the template lies in a Taylor variety, and is NP-complete otherwise. This paper provides two new characterizations of finitely generated Taylor varieties. The first characterization is using absorbing subalgebras and the second one cyclic terms. These new conditions allow us to reprove the conjecture of Bang-Jensen and Hell (proved by the authors) and the characterization of locally finite Taylor varieties using weak near-unanimity terms (proved by McKenzie and Mar\\'oti) in an elementary and self-contained way.<\/jats:p>","DOI":"10.2168\/lmcs-8(1:7)2012","type":"journal-article","created":{"date-parts":[[2012,9,6]],"date-time":"2012-09-06T10:03:11Z","timestamp":1346925791000},"source":"Crossref","is-referenced-by-count":58,"title":["Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem"],"prefix":"10.46298","volume":"Volume 8, Issue 1","author":[{"given":"Libor","family":"Barto","sequence":"first","affiliation":[]},{"given":"Marcin","family":"Kozik","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2012,2,20]]},"reference":[{"key":"10.2168\/LMCS-8(1:7)2012_conserv","doi-asserted-by":"crossref","unstructured":"Libor Barto. The dichotomy for conservative constraint satisfaction problems revisited. InProceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, LICS 2011, June 21-24, 2011, Toronto, Ontario, Canada, pages 301-310. IEEE Computer Society, 2011.","DOI":"10.1109\/LICS.2011.25"},{"key":"10.2168\/LMCS-8(1:7)2012_BD06","doi-asserted-by":"publisher","DOI":"10.1137\/050628957"},{"key":"10.2168\/LMCS-8(1:7)2012_BJH","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90017-7"},{"key":"10.2168\/LMCS-8(1:7)2012_BJK05","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"issue":"4","key":"10.2168\/LMCS-8(1:7)2012_cdbw","first-page":"1531","volume":"39","author":"Libor Barto and Marcin Kozik","year":"2009","journal-title":"SIAM Journal on Computing"},{"key":"10.2168\/LMCS-8(1:7)2012_bwproc","doi-asserted-by":"crossref","unstructured":"Libor Barto and Marcin Kozik. Constraint satisfaction problems of bounded width. InFOCS'09: Proceedings of the 50th Symposium on Foundations of Computer Science, pages 595-603, 2009.","DOI":"10.1109\/FOCS.2009.32"},{"key":"10.2168\/LMCS-8(1:7)2012_sdjoin","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-010-0094-z"},{"key":"10.2168\/LMCS-8(1:7)2012_BKJ00","doi-asserted-by":"crossref","unstructured":"Andrei A. Bulatov, Andrei A. Krokhin, and Peter Jeavons. Constraint satisfaction problems and finite algebras. InAutomata, languages and programming (Geneva, 2000), volume 1853 ofLecture Notes in Comput. Sci., pages 272-282. Springer, Berlin, 2000.","DOI":"10.1007\/3-540-45022-X_24"},{"key":"10.2168\/LMCS-8(1:7)2012_Dual1","unstructured":"V. G. Bodnar\u00c4\u008duk, L. A. Kaluznin, V. N. Kotov, and B. A. Romov. Galois theory for Post algebras. I, II.Kibernetika (Kiev), (3):1-10; ibid. 1969, no. 5, 1-9, 1969."},{"key":"10.2168\/LMCS-8(1:7)2012_firstcyclic","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-009-0025-z"},{"issue":"5","key":"10.2168\/LMCS-8(1:7)2012_smoothpaper","first-page":"1782","volume":"38","author":"Libor Barto, Marcin Kozik, and Todd Nive","year":"2008","journal-title":"SIAM J. Comput."},{"key":"10.2168\/LMCS-8(1:7)2012_smoothproc","doi-asserted-by":"crossref","unstructured":"Libor Barto, Marcin Kozik, and Todd Niven. Graphs, polymorphisms and the complexity of homomorphism problems. InSTOC '08: Proceedings of the 40th annual ACM symposium on Theory of computing, pages 789-796, New York, NY, USA, 2008. ACM.","DOI":"10.1145\/1374376.1374488"},{"key":"10.2168\/LMCS-8(1:7)2012_BS81","doi-asserted-by":"crossref","unstructured":"Stanley N. Burris and H. P. Sankappanavar.A course in universal algebra, volume 78 ofGraduate Texts in Mathematics. Springer-Verlag, New York, 1981.","DOI":"10.1007\/978-1-4613-8130-3"},{"key":"10.2168\/LMCS-8(1:7)2012_B03","doi-asserted-by":"crossref","unstructured":"Andrei A. Bulatov. Tractable conservative constraint satisfaction problems. In18th IEEE Symposium on Logic in Computer Science (LICS 2003), 22-25 June 2003, Ottawa, Canada, Proceedings, pages 321-. IEEE Computer Society, 2003.","DOI":"10.1109\/LICS.2003.1210072"},{"key":"10.2168\/LMCS-8(1:7)2012_B06","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"10.2168\/LMCS-8(1:7)2012_Bul11","first-page":"24","volume":"12","author":"Andrei A. Bulatov","year":"2011","journal-title":"ACM Trans. Comput. Logic"},{"issue":"4","key":"10.2168\/LMCS-8(1:7)2012_D06","first-page":"4","volume":"2","author":"V\u00edctor Dalmau","year":"2006","journal-title":"Log. Methods Comput. Sci."},{"issue":"1","key":"10.2168\/LMCS-8(1:7)2012_FV99","first-page":"57","volume":"28","author":"Tom\u00e1s Feder and Moshe Y. Vardi","year":"1999","journal-title":"SIAM J. Comput."},{"key":"10.2168\/LMCS-8(1:7)2012_Dual2","doi-asserted-by":"crossref","first-page":"95","DOI":"10.2140\/pjm.1968.27.95","volume":"27","author":"David Geiger","year":"1968","journal-title":"Pacific J. Math."},{"key":"10.2168\/LMCS-8(1:7)2012_TCTbook","doi-asserted-by":"crossref","unstructured":"David Hobby and Ralph McKenzie.The structure of finite algebras, volume 76 ofContemporary Mathematics. American Mathematical Society, Providence, RI, 1988.","DOI":"10.1090\/conm\/076"},{"key":"10.2168\/LMCS-8(1:7)2012_HN90","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"10.2168\/LMCS-8(1:7)2012_FewSPLICS","doi-asserted-by":"crossref","unstructured":"Pawel M. Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote, and Ross Willard. Tractability and learnability arising from algebras with few subpowers. InLICS, pages 213-224. IEEE Computer Society, 2007.","DOI":"10.1109\/LICS.2007.50"},{"key":"10.2168\/LMCS-8(1:7)2012_JCG97","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"10.2168\/LMCS-8(1:7)2012_KS09","doi-asserted-by":"crossref","unstructured":"G\u00e1bor Kun and Mario Szegedy. A new line of attack on the dichotomy conjecture. InProceedings of the 41st annual ACM symposium on Theory of computing, STOC '09, pages 725-734, New York, NY, USA, 2009. ACM.","DOI":"10.1145\/1536414.1536512"},{"key":"10.2168\/LMCS-8(1:7)2012_MM","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-008-2122-9"},{"key":"10.2168\/LMCS-8(1:7)2012_shaefer2","doi-asserted-by":"crossref","unstructured":"Thomas J. Schaefer. The complexity of satisfiability problems. InConference Record of the Tenth Annual ACMSymposium onTheory of Computing (San Diego, Calif., 1978), pages 216-226. ACM, New York, 1978.","DOI":"10.1145\/800133.804350"},{"key":"10.2168\/LMCS-8(1:7)2012_sig","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-010-0082-3"},{"key":"10.2168\/LMCS-8(1:7)2012_taylor","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1977-054-9"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/673\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/673\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T23:10:00Z","timestamp":1744067400000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/673"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,20]]},"references-count":28,"URL":"https:\/\/doi.org\/10.2168\/lmcs-8(1:7)2012","relation":{"is-same-as":[{"id-type":"arxiv","id":"1201.0557","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1201.0557","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2012,2,20]]},"article-number":"673"}}