{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T01:39:34Z","timestamp":1779154774062,"version":"3.51.4"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,10,19]],"date-time":"2007-10-19T00:00:00Z","timestamp":1192752000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2008,8]]},"DOI":"10.1007\/s00224-007-9083-9","type":"journal-article","created":{"date-parts":[[2007,10,18]],"date-time":"2007-10-18T13:50:33Z","timestamp":1192715433000},"page":"136-158","source":"Crossref","is-referenced-by-count":40,"title":["The Complexity of Equality Constraint Languages"],"prefix":"10.1007","volume":"43","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"K\u00e1ra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,10,19]]},"reference":[{"key":"9083_CR1","unstructured":"Allender, E., Bauland, M., Immerman, N., Schnoor, H., Vollmer, H.: The complexity of satisfiability problems: refining Schaefer\u2019s theorem. In: Electronical Colloquium on Computational Complexity, 2004"},{"key":"9083_CR2","unstructured":"Bodirsky, M.: Constraint satisfaction with infinite domains. PhD thesis, Humboldt-Universit\u00e4t zu Berlin (2004)"},{"key":"9083_CR3","series-title":"LNCS","first-page":"646","volume-title":"Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS\u201906)","author":"M. Bodirsky","year":"2006","unstructured":"Bodirsky, M., Dalmau, V.: Datalog and constraint satisfaction with infinite templates. In: Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS\u201906). LNCS, vol.\u00a03884, pp. 646\u2013659. Springer, Berlin (2006). A journal version is available from the webpage of the first author, 2006"},{"key":"9083_CR4","series-title":"LNCS","first-page":"114","volume-title":"Proceedings of the International Computer Science Symposium in Russia (CSR\u201906)","author":"M. Bodirsky","year":"2006","unstructured":"Bodirsky, M., K\u00e1ra, J.: The complexity of equality constraint languages. In: Proceedings of the International Computer Science Symposium in Russia (CSR\u201906). LNCS, vol.\u00a03967, pp. 114\u2013126. Springer, Berlin (2006)"},{"issue":"3","key":"9083_CR5","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1093\/logcom\/exi083","volume":"16","author":"M. Bodirsky","year":"2006","unstructured":"Bodirsky, M., Ne\u0161et\u0159il, J.: Constraint satisfaction with countable homogeneous templates. J. Log. Comput. 16(3), 359\u2013373 (2006)","journal-title":"J. Log. Comput."},{"key":"9083_CR6","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF01070906","volume":"5","author":"V.G. Bodnar\u010duk","year":"1969","unstructured":"Bodnar\u010duk, V.G., Kalu\u017enin, L.A., Kotov, V.N., Romov, B.A.: Galois theory for post algebras, part I and II. Cybernetics 5, 243\u2013539 (1969)","journal-title":"Cybernetics"},{"key":"9083_CR7","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A. Bulatov","year":"2005","unstructured":"Bulatov, A., Krokhin, A., Jeavons, P.G.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34, 720\u2013742 (2005)","journal-title":"SIAM J. Comput."},{"key":"9083_CR8","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511549809","volume-title":"Oligomorphic Permutation Groups","author":"P.J. Cameron","year":"1990","unstructured":"Cameron, P.J.: Oligomorphic Permutation Groups. Cambridge University Press, Cambridge (1990)"},{"issue":"5","key":"9083_CR9","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1145\/355483.355485","volume":"47","author":"D. Cohen","year":"2000","unstructured":"Cohen, D., Jeavons, P., Jonsson, P., Koubarakis, M.: Building tractable disjunctive constraints. J. ACM 47(5), 826\u2013853 (2000)","journal-title":"J. ACM"},{"key":"9083_CR10","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications, vol. 7 (2001)","DOI":"10.1137\/1.9780898718546"},{"issue":"1","key":"9083_CR11","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/S0304-3975(97)86737-0","volume":"173","author":"R. Dechter","year":"1997","unstructured":"Dechter, R., van Beek, P.: Local and global relational consistency. TCS 173(1), 283\u2013308 (1997)","journal-title":"TCS"},{"key":"9083_CR12","volume-title":"A Guide to NP-completeness","author":"M.R. Garey","year":"1978","unstructured":"Garey, M.R., Johnson, D.S.: A Guide to NP-completeness. CSLI Press, Stanford (1978)"},{"key":"9083_CR13","doi-asserted-by":"crossref","first-page":"95","DOI":"10.2140\/pjm.1968.27.95","volume":"27","author":"D. Geiger","year":"1968","unstructured":"Geiger, D.: Closed systems of functions and predicates. Pac. J. Math. 27, 95\u2013100 (1968)","journal-title":"Pac. J. Math."},{"key":"9083_CR14","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/PL00012450","volume":"48","author":"L. Heindorf","year":"2002","unstructured":"Heindorf, L.: The maximal clones on countable sets that include all permutations. Algebra Universalis 48, 209\u2013222 (2002)","journal-title":"Algebra Universalis"},{"key":"9083_CR15","volume-title":"A Shorter Model Theory","author":"W. Hodges","year":"1997","unstructured":"Hodges, W.: A Shorter Model Theory. Cambridge University Press, Cambridge (1997)"},{"key":"9083_CR16","unstructured":"Krasner, M.: G\u00e9n\u00e9ralisation et analogues de la th\u00e9orie de Galois. In: Congr\u00e9s de la Victoire de l\u2019Ass. France avancement des sciences, pp.\u00a0 54\u201358, 1945"},{"issue":"1","key":"9083_CR17","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/200836.200848","volume":"42","author":"B. Nebel","year":"1995","unstructured":"Nebel, B., B\u00fcrckert, H.-J.: Reasoning about temporal relations: a maximal tractable subclass of Allen\u2019s interval algebra. J. ACM 42(1), 43\u201366 (1995)","journal-title":"J. ACM"},{"key":"9083_CR18","unstructured":"Ottmann, T., Widmayer, P.: Algorithmen und Datenstrukturen. Spektrum Akademischer Verlag (2002)"},{"issue":"2","key":"9083_CR19","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/s00012-005-1929-x","volume":"54","author":"M. Pinsker","year":"2005","unstructured":"Pinsker, M.: Maximal clones on uncountable sets that include all permutations. Algebra Universalis 54(2), 129\u2013148 (2005)","journal-title":"Algebra Universalis"},{"key":"9083_CR20","first-page":"461","volume":"71","author":"M. Pinsker","year":"2005","unstructured":"Pinsker, M.: The number of unary clones containing the permutations on an infinite set. Acta Sci. Math. (Szeged) 71, 461\u2013467 (2005)","journal-title":"Acta Sci. Math. (Szeged)"},{"issue":"2","key":"9083_CR21","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/s00012-005-1929-x","volume":"54","author":"M. Pinsker","year":"2005","unstructured":"Pinsker, M.: Maximal clones on uncountable sets that include all permutations. Algebra Universalis 54(2), 129\u2013148 (2005)","journal-title":"Algebra Universalis"},{"key":"9083_CR22","doi-asserted-by":"crossref","unstructured":"P\u00f6schel, R., Kalu\u017enin, L.A.: Funktionen- und Relationenalgebren. Deutscher Verlag der Wissenschaften (1979)","DOI":"10.1007\/978-3-0348-5547-1"},{"key":"9083_CR23","unstructured":"Szendrei, A.: Clones in universal Algebra. Seminaire de mathematiques superieures. Les Presses de L\u2019Universite de Montreal (1986)"},{"key":"9083_CR24","doi-asserted-by":"crossref","unstructured":"Valiant, L., Vazirani, V.: NP is as easy as detecting unique solutions. In: Proc. ACM Symp. on Theory of Computing, 1985","DOI":"10.1145\/22145.22196"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9083-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9083-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9083-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:51:35Z","timestamp":1558684295000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9083-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,19]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["9083"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9083-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,19]]}}}