{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:38Z","timestamp":1760202578689},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540927990"},{"type":"electronic","value":"9783540928003"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-92800-3_4","type":"book-chapter","created":{"date-parts":[[2008,12,22]],"date-time":"2008-12-22T03:39:25Z","timestamp":1229917165000},"page":"68-92","source":"Crossref","is-referenced-by-count":32,"title":["Recent Results on the Algebraic Approach to the CSP"],"prefix":"10.1007","author":[{"given":"Andrei A.","family":"Bulatov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew A.","family":"Valeriote","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/11549345_8","volume-title":"Mathematical Foundations of Computer Science 2005","author":"E. Allender","year":"2005","unstructured":"Allender, E., Bauland, M., Immerman, N., Schnoor, H., Vollmer, H.: The complexity of satisfiability problems: Refining schaefer\u2019s theorem. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 71\u201382. Springer, Heidelberg (2005)"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Berman, J., Idziak, P., Markovi\u0107, P., McKenzie, R., Valeriote, M., Willard, R.: Varieties with few subalgebras of powers. Journal of the AMS (to appear)","DOI":"10.1090\/S0002-9947-09-04874-0"},{"issue":"1-3","key":"4_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0012-365X(93)90219-J","volume":"112","author":"J.D. Berman","year":"1993","unstructured":"Berman, J.D., Kiss, E.W., Pr\u00f6hle, P., Szendrei, \u00c1.: The set of types of a finitely generated variety. Discrete Math.\u00a0112(1-3), 1\u201320 (1993)","journal-title":"Discrete Math."},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/BF01187059","volume":"143","author":"K.A. Baker","year":"1975","unstructured":"Baker, K.A., Pixley, A.F.: Polynomial interpolation and the chinese remainder theorem. Mathematische Zeitschrift\u00a0143, 165\u2013174 (1975)","journal-title":"Mathematische Zeitschrift"},{"key":"4_CR5","unstructured":"Bulatov, A.A.: Mal\u2019tsev constraints are tractable. Technical Report PRG-RR-02-05, Computing Laboratory, University of Oxford, Oxford, UK (2002)"},{"issue":"2","key":"4_CR6","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/j.jalgebra.2004.07.044","volume":"298","author":"A.A. Bulatov","year":"2006","unstructured":"Bulatov, A.A.: Combinatorial problems raised from 2-semilattices. Journal of Algebra\u00a0298(2), 321\u2013339 (2006)","journal-title":"Journal of Algebra"},{"key":"4_CR7","unstructured":"Bulatov, A.A., Jeavons, P.G.: Tractable constraints closed under a binary operation. Technical Report PRG-TR-12-00, Computing Laboratory, University of Oxford, Oxford, UK (2000)"},{"key":"4_CR8","unstructured":"Bulatov, A.A., Jeavons, P.G.: Algebraic structures in combinatorial problems. Technical Report MATH-AL-4-2001, Technische universit\u00e4t Dresden, Dresden, Germany (2001), http:\/\/web.comlab.ox.ac.uk\/oucl\/research\/areas\/constraints\/publications\/index.html"},{"key":"4_CR9","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1142\/9789812776884_0011","volume-title":"Semigroups, Algorithms, Automata and Languages","author":"A.A. Bulatov","year":"2002","unstructured":"Bulatov, A.A., Jeavons, P.G., Volkov, M.V.: Finite semigroups imposing tractable constraints. In: Gomes, G.M.S., Pin, J.-E., Silva, P.V. (eds.) Semigroups, Algorithms, Automata and Languages, pp. 313\u2013329. World Scientific, Singapore (2002)"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: A graph of a relational structure and constraint satisfaction problems. In: LICS, pp. 448\u2013457 (2004)","DOI":"10.1109\/LICS.2004.1319639"},{"issue":"1","key":"4_CR11","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.tcs.2005.09.028","volume":"349","author":"A.A. Bulatov","year":"2005","unstructured":"Bulatov, A.A.: H-coloring dichotomy revisited. Theor. Comput. Sci.\u00a0349(1), 31\u201339 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"4_CR12","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"A.A. Bulatov","year":"2006","unstructured":"Bulatov, A.A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM\u00a053(1), 66\u2013120 (2006)","journal-title":"J. ACM"},{"issue":"1","key":"4_CR13","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1137\/050628957","volume":"36","author":"A.A. Bulatov","year":"2006","unstructured":"Bulatov, A.A., Dalmau, V.: A simple algorithm for Mal\u2019tsev constraints. SIAM J. Comput.\u00a036(1), 16\u201327 (2006)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"4_CR14","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A.A. Bulatov","year":"2005","unstructured":"Bulatov, A.A., Jeavons, P., Krokhin, A.A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput.\u00a034(3), 720\u2013742 (2005)","journal-title":"SIAM J. Comput."},{"key":"4_CR15","series-title":"Lecture Notes in Computer Science","volume-title":"Automata, Languages and Programming","author":"A. Atserias","year":"2007","unstructured":"Atserias, A., Bulatov, A., Dawar, A.: Affine systems of equations and counting infinitary logic. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596. Springer, Heidelberg (2007)"},{"key":"4_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-540-92800-3_5","volume-title":"Complexity of Constraints","author":"A.A. Bulatov","year":"2008","unstructured":"Bulatov, A.A., Krokhin, A.A., Larose, B.: Dualities for Constraint Satisfaction Problems. In: Creignou, N., Kolaitis, P., Vollmer, H. (eds.) Complexity of Constraints. LNCS, vol.\u00a05250, pp. 93\u2013124. Springer, Heidelberg (2008)"},{"key":"4_CR17","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-8130-3","volume-title":"A course in universal algebra","author":"S. Burris","year":"1981","unstructured":"Burris, S., Sankappanavar, H.P.: A course in universal algebra. Graduate Texts in Mathematics, vol.\u00a078. Springer, New York (1981)"},{"issue":"4","key":"4_CR18","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s10472-005-7031-4","volume":"44","author":"H. Chen","year":"2005","unstructured":"Chen, H.: The expressive rate of constraints. Ann. Math. Artif. Intell.\u00a044(4), 341\u2013352 (2005)","journal-title":"Ann. Math. Artif. Intell."},{"key":"4_CR19","series-title":"Fields Inst. Monogr.","first-page":"67","volume-title":"Lectures on algebraic model theory","author":"M. Clasen","year":"2002","unstructured":"Clasen, M., Valeriote, M.: Tame congruence theory. In: Lectures on algebraic model theory. Fields Inst. Monogr., vol.\u00a015, pp. 67\u2013111. Amer. Math. Soc., Providence (2002)"},{"issue":"1-2","key":"4_CR20","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s10472-005-1810-9","volume":"44","author":"V. Dalmau","year":"2005","unstructured":"Dalmau, V.: A new tractable class of constraint satisfaction problems. Annals of Mathematics and Artificial Intelligence\u00a044(1-2), 61\u201385 (2005)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"4_CR21","unstructured":"Dalmau, V.: Computational Complexity of Problems over Generalised Formulas. Ph.D thesis, Department LSI of the Universitat Politecnica de Catalunya (UPC), Barcelona (March 2000)"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Dalmau, V.: Generalized majority-minority operations are tractable. In: LICS, pp. 438\u2013447 (2005)","DOI":"10.2168\/LMCS-2(4:1)2006"},{"key":"4_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/11564751_17","volume-title":"Principles and Practice of Constraint Programming - CP 2005","author":"V. Dalmau","year":"2005","unstructured":"Dalmau, V., Gavald\u00e0, R., Tesson, P., Th\u00e9rien, D.: Tractable clones of polynomials over semigroups. In: van Beek, P. (ed.) CP 2005. LNCS, vol.\u00a03709, pp. 196\u2013210. Springer, Heidelberg (2005)"},{"key":"4_CR24","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\u00a028, 57\u2013104 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR25","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, Ser. B\u00a048, 92\u2013110 (1990)","journal-title":"Journal of Combinatorial Theory, Ser. B"},{"key":"4_CR26","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","DOI":"10.1090\/conm\/076","volume-title":"The Structure of Finite Algebras","author":"D. Hobby","year":"1988","unstructured":"Hobby, D., McKenzie, R.N.: The Structure of Finite Algebras. Contemporary Mathematics, vol.\u00a076. American Mathematical Society, Providence (1988)"},{"key":"4_CR27","first-page":"213","volume-title":"LICS 2007: Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science","author":"P. Idziak","year":"2007","unstructured":"Idziak, P., Markovi\u0107, P., McKenzie, R., Valeriote, M., Willard, R.: Tractability and learnability arising from algebras with few subpowers. In: LICS 2007: Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science, Washington, DC, USA, pp. 213\u2013224. IEEE Computer Society, Los Alamitos (2007)"},{"key":"4_CR28","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"P.G. Jeavons","year":"1998","unstructured":"Jeavons, P.G.: On the algebraic structure of combinatorial problems. Theoretical Computer Science\u00a0200, 185\u2013204 (1998)","journal-title":"Theoretical Computer Science"},{"issue":"1-2","key":"4_CR29","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0004-3702(98)00022-8","volume":"101","author":"P.G. Jeavons","year":"1998","unstructured":"Jeavons, P.G., Cohen, D.A., Cooper, M.C.: Constraints, consistency and closure. Artificial Intelligence\u00a0101(1-2), 251\u2013265 (1998)","journal-title":"Artificial Intelligence"},{"key":"4_CR30","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P.G. Jeavons","year":"1997","unstructured":"Jeavons, P.G., Cohen, D.A., Gyssens, M.: Closure properties of constraints. Journal of the ACM\u00a044, 527\u2013548 (1997)","journal-title":"Journal of the ACM"},{"key":"4_CR31","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1023\/A:1018941030227","volume":"24","author":"P.G. Jeavons","year":"1998","unstructured":"Jeavons, P.G., Cohen, D.A., Pearson, J.K.: Constraints and universal algebra. Annals of Mathematics and Artificial Intelligence\u00a024, 51\u201367 (1998)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"4_CR32","doi-asserted-by":"crossref","unstructured":"Larose, B., Loten, C., Tardif, C.: A characterisation of first-order constraint satisfaction problems. In: LICS, pp. 201\u2013210 (2006)","DOI":"10.1109\/LICS.2006.6"},{"key":"4_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-540-73420-8_25","volume-title":"Automata, Languages and Programming","author":"B. Larose","year":"2007","unstructured":"Larose, B., Tesson, P.: Universal algebra and hardness results for constraint satisfaction problems. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 267\u2013278. Springer, Heidelberg (2007)"},{"issue":"3-4","key":"4_CR34","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/s00012-007-2012-6","volume":"56","author":"B. Larose","year":"2007","unstructured":"Larose, B., Zadori, L.: Bounded width problems and algebras. Algebra Universalis\u00a056(3-4), 439\u2013466 (2007)","journal-title":"Algebra Universalis"},{"issue":"2","key":"4_CR35","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s00012-008-2049-1","volume":"58","author":"P. Markovi\u0107","year":"2008","unstructured":"Markovi\u0107, P., McKenzie, R.: Few subpowers, congruence distributivity and near-unanimity. Algebra Universalis\u00a058(2), 119\u2013128 (2008)","journal-title":"Algebra Universalis"},{"key":"4_CR36","volume-title":"Algebras, Lattices and Varieties","author":"R.N. McKenzie","year":"1987","unstructured":"McKenzie, R.N., McNulty, G.F., Taylor, W.F.: Algebras, Lattices and Varieties, vol.\u00a0I. Wadsworth and Brooks, California (1987)"},{"key":"4_CR37","unstructured":"McKenzie, R., Mar\u00f3ti, M.: Existence theorems for weakly symmetric operations. In: Algebra Universalis (to appear, 2006)"},{"key":"4_CR38","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th ACM Symposium on Theory of Computing (STOC 1978), pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"4_CR39","unstructured":"Szendrei, A.: Clones in Universal Algebra. Seminaires de Mathematiques Superieures, vol.\u00a099. Universit\u00e9 de M\u00f3ntreal (1986)"},{"key":"4_CR40","unstructured":"Valeriote, M.: A subalgebra intersection property for congruence distributive varieties. Canadian Journal of Mathematics (accepted, 2006)"}],"container-title":["Lecture Notes in Computer Science","Complexity of Constraints"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-92800-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,22]],"date-time":"2023-05-22T23:10:29Z","timestamp":1684797029000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92800-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540927990","9783540928003"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92800-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}