{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T12:52:39Z","timestamp":1773406359294,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540734192","type":"print"},{"value":"9783540734208","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73420-8_25","type":"book-chapter","created":{"date-parts":[[2007,8,25]],"date-time":"2007-08-25T14:58:43Z","timestamp":1188053923000},"page":"267-278","source":"Crossref","is-referenced-by-count":6,"title":["Universal Algebra and Hardness Results for Constraint Satisfaction Problems"],"prefix":"10.1007","author":[{"given":"Beno\u00eet","family":"Larose","sequence":"first","affiliation":[]},{"given":"Pascal","family":"Tesson","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"25_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":"25_CR2","doi-asserted-by":"crossref","unstructured":"Atserias, A.: On digraph coloring problems and treewidth duality. In: Proc.\u00a021st Conf.\u00a0on Logic in Comp.\u00a0Sci.\u00a0(LICS 2005), pp. 106\u2013115 (2005)","DOI":"10.1109\/LICS.2005.31"},{"key":"25_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/3-540-45022-X_24","volume-title":"Automata, Languages and Programming","author":"A. Bulatov","year":"2000","unstructured":"Bulatov, A., Krokhin, A., Jeavons, P.: Constraint satisfaction problems and finite algebras. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 272\u2013282. Springer, Heidelberg (2000)"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"Cohen, D., Jeavons, P.G.: The complexity of constraint languages. In: Handbook of Constraint Programming (2006)","DOI":"10.1016\/S1574-6526(06)80012-X"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"Dalmau, V.: Linear Datalog and bounded path duality of relational structures. Logical Methods in Computer Science\u00a01(1) (2005)","DOI":"10.2168\/LMCS-1(1:5)2005"},{"key":"25_CR6","unstructured":"Dalmau, V., Egri, L., Larose, B., Tesson, P.: On the limits of expressivity of linear and symmetric Datalog. Document in preparation (2007)"},{"key":"25_CR7","doi-asserted-by":"crossref","DOI":"10.1201\/9781315273686","volume-title":"Universal Algebra and Applications in Theoretical Computer Science","author":"K. Denecke","year":"2002","unstructured":"Denecke, K., Wismath, S.L.: Universal Algebra and Applications in Theoretical Computer Science. CRC\/C&H, Boca Raton (2002)"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"Egri, L., Larose, B., Tesson, P.: Symmetric datalog and constraint satisfaction problems in logspace (Submitted, 2007)","DOI":"10.1109\/LICS.2007.47"},{"issue":"1","key":"25_CR9","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1999","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM J. on Computing\u00a028(1), 57\u2013104 (1999)","journal-title":"SIAM J. on Computing"},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"Feder, T., Vardi, M.Y.: Homomorphism closed vs. existential positive. In: Feder, T., Vardi, M.Y. (eds.) Proc. 18th Symp. on Logic in Comp. Sci (LICS 2003), pp. 311\u2013320 (2003)","DOI":"10.1109\/LICS.2003.1210071"},{"key":"25_CR11","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.: The Structure of Finite Algebras. Contemporary Mathematics, vol.\u00a076. American Mathematical Society, New York (1988)"},{"key":"25_CR12","series-title":"Graduate Texts in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N. Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive Complexity. Graduate Texts in Computer Science. Springer, Heidelberg (1999)"},{"issue":"1-2","key":"25_CR13","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P.: On the algebraic structure of combinatorial problems. Theor. Comput. Sci.\u00a0200(1-2), 185\u2013204 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"25_CR14","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1006\/jcss.1995.1055","volume":"51","author":"P.G. Kolaitis","year":"1995","unstructured":"Kolaitis, P.G., Vardi, M.Y.: On the expressive power of datalog: Tools and a case study. J. Comput. Syst. Sci.\u00a051(1), 110\u2013134 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"25_CR15","doi-asserted-by":"crossref","unstructured":"Larose, B., Loten, C., Tardif, C.: A characterization of first-order constraint satisfaction problems. In: Proc. 21st Symp. on Logic in Comp, pp. 201\u2013210 (2006)","DOI":"10.1109\/LICS.2006.6"},{"issue":"2-3","key":"25_CR16","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s00012-004-1819-7","volume":"52","author":"B. Larose","year":"2005","unstructured":"Larose, B., Z\u00e1dori, L.: Finite posets and topological spaces in locally finite varieties. Algebra Universalis\u00a052(2-3), 119\u2013136 (2005)","journal-title":"Algebra Universalis"},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"Larose, B., Z\u00e1dori, L.: Bounded width problems and algebras. Algebra Universalis (2006)","DOI":"10.1007\/s00012-007-2012-6"},{"key":"25_CR18","first-page":"216","volume-title":"Proc. 10 th ACM STOC","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proc. 10 th ACM STOC, pp. 216\u2013226. ACM Press, New York (1978)"},{"key":"25_CR19","unstructured":"Szendrei, A.: A survey on strictly simple algebras and minimal varieties. Research and Exposition in Mathematics, pp. 209\u2013239. Heldermann Verlag (1992)"},{"key":"25_CR20","doi-asserted-by":"crossref","unstructured":"Valeriote, M.: A subalgebra intersection property for congruence distributive varieties. In: Canadian J.\u00a0of Math. (to appear)","DOI":"10.4153\/CJM-2009-023-2"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73420-8_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T17:15:39Z","timestamp":1737393339000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73420-8_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540734192","9783540734208"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73420-8_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}