{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:56:58Z","timestamp":1725469018749},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540377917"},{"type":"electronic","value":"9783540377931"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11821069_51","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T10:25:12Z","timestamp":1156501512000},"page":"584-595","source":"Crossref","is-referenced-by-count":1,"title":["Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture"],"prefix":"10.1007","author":[{"given":"Ond\u0159ej","family":"Kl\u00edma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Beno\u00eet","family":"Larose","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Tesson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"51_CR1","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: A dichotomy theorem for constraints on a three-element set. In: Proc. of 43rd Foundations of Comp. Sci. (FOCS 2002), pp. 649\u2013658 (2002)","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"51_CR2","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: Tractable conservative constraint satisfaction problems. In: 18th IEEE Symp.\u00a0on Logic in Comp.\u00a0Sci.\u00a0(LICS 2003), pp. 321\u2013331 (2003)","DOI":"10.1109\/LICS.2003.1210072"},{"key":"51_CR3","doi-asserted-by":"crossref","unstructured":"Bulatov, A., Dalmau, V.: Towards a dichotomy theorem for the counting constraint satisfaction problem. In: 44th IEEE Symp.\u00a0on Foundations of Comp.\u00a0Sci.\u00a0(FOCS 2003), pp. 562\u2013571 (2003)","DOI":"10.1109\/SFCS.2003.1238229"},{"issue":"1","key":"51_CR4","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1137\/050628957","volume":"36","author":"A. Bulatov","year":"2006","unstructured":"Bulatov, A., Dalmau, V.: A simple algorithm for mal\u2019tsev constraints. SIAM J. Comput.\u00a036(1), 16\u201327 (2006)","journal-title":"SIAM J. Comput."},{"key":"51_CR5","doi-asserted-by":"crossref","unstructured":"Bulatov, A., Dalmau, V.: Towards a dichotomy theorem for the counting constraint satisfaction problem (to appear, 2006)","DOI":"10.1016\/j.ic.2006.09.005"},{"key":"51_CR6","doi-asserted-by":"crossref","unstructured":"Bulatov, A., Grohe, M.: The complexity of partition functions. In: Proc.\u00a031st Int.\u00a0Coll.\u00a0on Automata Languages and Programming, pp. 294\u2013306 (2004)","DOI":"10.1007\/978-3-540-27836-8_27"},{"key":"51_CR7","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)"},{"issue":"1","key":"51_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0016","volume":"125","author":"N. Creignou","year":"1996","unstructured":"Creignou, N., Hermann, M.: Complexity of generalized satisfiability counting problems. Inf. Comput.\u00a0125(1), 1\u201312 (1996)","journal-title":"Inf. Comput."},{"key":"51_CR9","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\u00e1, 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)"},{"issue":"1","key":"51_CR10","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":"51_CR11","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198511946.001.0001","volume-title":"Fundamentals of Semigroup Theory","author":"J. Howie","year":"1995","unstructured":"Howie, J.: Fundamentals of Semigroup Theory. Claredon Press, Oxford (1995)"},{"issue":"1-2","key":"51_CR12","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":"4","key":"51_CR13","first-page":"527","volume":"44","author":"P. Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: Closure properties of constraints. J.\u00a0ACM\u00a044(4), 527\u2013548 (1997)","journal-title":"J.\u00a0ACM"},{"key":"51_CR14","doi-asserted-by":"crossref","unstructured":"Kl\u00edma, O., Tesson, P., Th\u00e9rien, D.: Dichotomies in the complexity of solving systems of equations over finite semigroups. Theory of Computing Systems (2006)","DOI":"10.1007\/s00224-005-1279-2"},{"key":"51_CR15","doi-asserted-by":"crossref","unstructured":"Larose, B., Z\u00e1dori, L.: Taylor terms, constraint satisfaction and the complexity of polynomial equations over finite algebras. Internat.\u00a0J.\u00a0Algebra and Computation, 17 (2006) (to appear)","DOI":"10.1142\/S0218196706003116"},{"key":"51_CR16","unstructured":"McKenzie, R., McNulty, G., Taylor, W.: Algebras, Lattices and Varieties. Wadsworth and Brooks\/Cole (1987)"},{"key":"51_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1007\/978-3-540-28629-5_28","volume-title":"Mathematical Foundations of Computer Science 2004","author":"G. Nordh","year":"2004","unstructured":"Nordh, G.: The complexity of equivalence and isomorphism of systems of equations over finite groups. In: Fiala, J., Koubek, V., Kratochv\u00edl, J. (eds.) MFCS 2004. LNCS, vol.\u00a03153, pp. 380\u2013391. Springer, Heidelberg (2004)"},{"key":"51_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/978-3-540-27798-9_40","volume-title":"Computing and Combinatorics","author":"G. Nordh","year":"2004","unstructured":"Nordh, G., Jonsson, P.: The complexity of counting solutions to systems of equations over finite semigroups. In: Chwa, K.-Y., Munro, J.I.J. (eds.) COCOON 2004. LNCS, vol.\u00a03106, pp. 370\u2013379. Springer, Heidelberg (2004)"},{"key":"51_CR19","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proc. 10th ACM STOC, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"51_CR20","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci.\u00a08, 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11821069_51.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,6]],"date-time":"2024-02-06T02:43:37Z","timestamp":1707187417000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11821069_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540377917","9783540377931"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11821069_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}