{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T12:09:12Z","timestamp":1773144552033,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540705826","type":"print"},{"value":"9783540705833","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70583-3_16","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"184-196","source":"Crossref","is-referenced-by-count":43,"title":["Non-dichotomies in Constraint Satisfaction Complexity"],"prefix":"10.1007","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"16_CR1","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1006\/jctb.1994.1040","volume":"61","author":"B.L. Bauslaugh","year":"1994","unstructured":"Bauslaugh, B.L.: The complexity of infinite h-coloring. J. Comb. Theory, Ser. B\u00a061(2), 141\u2013154 (1994)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Bodirsky, M.: Constraint satisfaction problems with infinite templates. Survey (to appear, 2007)","DOI":"10.1007\/978-3-540-92800-3_8"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: Tractable conservative constraint satisfaction problems. In: Proceedings of LICS 2003, pp. 321\u2013330 (2003)","DOI":"10.1109\/LICS.2003.1210072"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: A graph of a relational structure and constraint satisfaction problems. In: Proceedings of LICS 2004, Turku, Finland (2004)","DOI":"10.1109\/LICS.2004.1319639"},{"key":"16_CR5","unstructured":"Bulatov, A., Jeavons, P.: Algebraic structures in combinatorial problems. Technical report MATH-AL-4-2001, Technische Universitat Dresden, submitted to International Journal of Algebra and Computing (2001)"},{"key":"16_CR6","doi-asserted-by":"publisher","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 Journal on Computing\u00a034, 720\u2013742 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR7","series-title":"Lecture Notes in Computer Science","volume-title":"ICALP 2008","author":"Y. Chen","year":"2008","unstructured":"Chen, Y., Thurley, M., Weyer, M.: Understanding the complexity of induced substructure isomorphisms. In: Aceto, L., Damgaard, I., Goldberg, L.A., Halldorsson, M.M., Ingolfsdottir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol.\u00a05125. Springer, Heidelberg (2008)"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Cherlin, G.: The classification of countable homogeneous directed graphs and countable homogeneous n-tournaments. AMS Memoir.\u00a0131(621) (January 1998)","DOI":"10.1090\/memo\/0621"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1999","unstructured":"Feder, T., Vardi, M.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal on Computing\u00a028, 57\u2013104 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM\u00a054(1) (2007)","DOI":"10.1145\/1206035.1206036"},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"494","DOI":"10.2307\/2272734","volume":"37","author":"C.W. Henson","year":"1972","unstructured":"Henson, C.W.: Countable homogeneous relational systems and categorical theories. Journal of Symbolic Logic\u00a037, 494\u2013500 (1972)","journal-title":"Journal of Symbolic Logic"},{"key":"16_CR12","volume-title":"A shorter model theory","author":"W. Hodges","year":"1997","unstructured":"Hodges, W.: A shorter model theory. Cambridge University Press, Cambridge (1997)"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"Idziak, P.M., Markovic, P., McKenzie, R., Valeriote, M., Willard, R.: Tractability and learnability arising from algebras with few subpowers. In: LICS 2007, pp. 213\u2013224 (2007)","DOI":"10.1109\/LICS.2007.50"},{"issue":"1","key":"16_CR14","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: On the structure of polynomial time reducibility. J. ACM\u00a022(1), 155\u2013171 (1975)","journal-title":"J. ACM"},{"issue":"1","key":"16_CR15","doi-asserted-by":"publisher","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\u00a042(1), 43\u201366 (1995)","journal-title":"J. ACM"},{"key":"16_CR16","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"16_CR17","unstructured":"Schwandtner, G.: Datalog on infinite structures. Dissertation, Humboldt-Universit\u00e4t zu Berlin (submitted, 2008)"}],"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-70583-3_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:07:56Z","timestamp":1605762476000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70583-3_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540705826","9783540705833"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70583-3_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}