{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T22:39:30Z","timestamp":1791239970928,"version":"4.1.0"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319449524","type":"print"},{"value":"9783319449531","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-44953-1_9","type":"book-chapter","created":{"date-parts":[[2016,8,22]],"date-time":"2016-08-22T15:12:23Z","timestamp":1471878743000},"page":"130-146","source":"Crossref","is-referenced-by-count":4,"title":["The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable"],"prefix":"10.1007","author":[{"given":"Cl\u00e9ment","family":"Carbonnel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,8,23]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"Barto, L.: The dichotomy for conservative constraint satisfaction problems revisited. In: LICS, pp. 301\u2013310. IEEE Computer Society (2011)","DOI":"10.1109\/LICS.2011.25"},{"key":"9_CR2","doi-asserted-by":"crossref","first-page":"923","DOI":"10.1093\/logcom\/exu070","volume":"26","author":"L Barto","year":"2015","unstructured":"Barto, L.: The collapse of the bounded width hierarchy. J. Logic Comput. 26, 923\u2013943 (2015)","journal-title":"J. Logic Comput."},{"issue":"3","key":"9_CR3","doi-asserted-by":"crossref","first-page":"1445","DOI":"10.1090\/S0002-9947-09-04874-0","volume":"362","author":"J Berman","year":"2010","unstructured":"Berman, J., Idziak, P., Markovi\u0107, P., McKenzie, R., Valeriote, M., Willard, R.: Varieties with few subalgebras of powers. Trans. Am. Math. Soc. 362(3), 1445\u20131473 (2010)","journal-title":"Trans. Am. Math. Soc."},{"key":"9_CR4","unstructured":"Bessi\u00e8re, C., Carbonnel, C., H\u00e9brard, E., Katsirelos, G., Walsh, T.: Detecting and exploiting subproblem tractability. In: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, pp. 468\u2013474. AAAI Press (2013)"},{"issue":"4","key":"9_CR5","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/1970398.1970400","volume":"12","author":"AA Bulatov","year":"2011","unstructured":"Bulatov, A.A.: Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log. 12(4), 24 (2011)","journal-title":"ACM Trans. Comput. Log."},{"key":"9_CR6","unstructured":"Bulatov, A.A.: Conservative constraint satisfaction re-revisited. preprint. arXiv:1408.3690v1 (2014)"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Carbonnel, C.: The meta-problem for conservative Mal\u2019tsev constraints. In: Thirtieth AAAI Conference on Artificial Intelligence (AAAI 2016), Phoenix, Arizona, United States, February 2016","DOI":"10.1609\/aaai.v30i1.10432"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"Chen, H., Larose, B.: Asking the metaquestions in constraint tractability. arXiv preprint. arXiv:1604.00932 (2016)","DOI":"10.1145\/3134757"},{"issue":"4","key":"9_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2168\/LMCS-2(4:1)2006","volume":"2","author":"V Dalmau","year":"2006","unstructured":"Dalmau, V.: Generalized majority-minority operations are tractable. Logical Methods Comput. Sci. 2(4), 1\u201315 (2006)","journal-title":"Logical Methods Comput. Sci."},{"issue":"1","key":"9_CR10","doi-asserted-by":"crossref","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 J. Comput. 28(1), 57\u2013104 (1998)","journal-title":"SIAM J. Comput."},{"issue":"8\u20139","key":"9_CR11","doi-asserted-by":"crossref","first-page":"1094","DOI":"10.1016\/j.artint.2007.12.001","volume":"172","author":"MJ Green","year":"2008","unstructured":"Green, M.J., Cohen, D.A.: Domain permutation reduction for constraint satisfaction problems. Artif. Intell. 172(8\u20139), 1094\u20131118 (2008)","journal-title":"Artif. Intell."},{"key":"9_CR12","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, pp. 213\u2013224. IEEE Computer Society (2007)","DOI":"10.1109\/LICS.2007.50"},{"issue":"4","key":"9_CR13","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D.A., Gyssens, M.: Closure properties of constraints. J. ACM 44(4), 527\u2013548 (1997)","journal-title":"J. ACM"},{"key":"9_CR14","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"PG Jeavons","year":"1998","unstructured":"Jeavons, P.G.: On the algebraic structure of combinatorial problems. Theoret. Comput. Sci. 200, 185\u2013204 (1998)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"9_CR15","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"RE Ladner","year":"1975","unstructured":"Ladner, R.E.: On the structure of polynomial time reducibility. J. ACM 22(1), 155\u2013171 (1975)","journal-title":"J. ACM"},{"key":"9_CR16","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"AK Mackworth","year":"1977","unstructured":"Mackworth, A.K.: Consistency in networks of relations. Artif. Intell. 8, 99\u2013118 (1977)","journal-title":"Artif. Intell."},{"key":"9_CR17","series-title":"Annals Mathematical Studies","volume-title":"The Two-Valued Iterative Systems of Mathematical Logic","author":"EL Post","year":"1941","unstructured":"Post, E.L.: The Two-Valued Iterative Systems of Mathematical Logic. Annals Mathematical Studies, vol. 5. Princeton University Press, Princeton (1941)"},{"issue":"1\u20132","key":"9_CR18","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/s00012-010-0082-3","volume":"64","author":"MH Siggers","year":"2010","unstructured":"Siggers, M.H.: A strong malcev condition for locally finite varieties omitting the unary type. Algebra Univers. 64(1\u20132), 15\u201320 (2010)","journal-title":"Algebra Univers."},{"key":"9_CR19","first-page":"1173","volume-title":"IJCAI","author":"R Williams","year":"2003","unstructured":"Williams, R., Gomes, C.P., Selman, B.: Backdoors to typical case complexity. In: Gottlob, G., Walsh, T. (eds.) IJCAI, pp. 1173\u20131178. Morgan Kaufmann, San Francisco (2003)"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-44953-1_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,6]],"date-time":"2022-07-06T21:21:09Z","timestamp":1657142469000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-44953-1_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319449524","9783319449531"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-44953-1_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}