{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:48:10Z","timestamp":1787507290497,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540454588","type":"print"},{"value":"9783540454595","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11874683_13","type":"book-chapter","created":{"date-parts":[[2006,9,27]],"date-time":"2006-09-27T09:47:26Z","timestamp":1159350446000},"page":"197-211","source":"Crossref","is-referenced-by-count":3,"title":["Collapsibility in Infinite-Domain Quantified Constraint Satisfaction"],"prefix":"10.1007","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hubie","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"13_CR1","unstructured":"Bodirsky, M.: Constraint satisfaction with infinite domains. Ph.D. thesis, Humboldt-Universit\u00e4t zu Berlin (2004)"},{"key":"13_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/978-3-540-31856-9_9","volume-title":"STACS 2005","author":"M. Bodirsky","year":"2005","unstructured":"Bodirsky, M.: The core of a countably categorical structure. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 100\u2013110. Springer, Heidelberg (2005)"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Chen, H.: Quantified equality constraints (manuscript, 2006)","DOI":"10.1109\/LICS.2007.38"},{"key":"13_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/11753728_14","volume-title":"Computer Science \u2013 Theory and Applications","author":"M. Bodirsky","year":"2006","unstructured":"Bodirsky, M., K\u00e1ra, J.: The complexity of equality constraint languages. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds.) CSR 2006. LNCS, vol.\u00a03967, pp. 114\u2013126. Springer, Heidelberg (2006)"},{"key":"13_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/978-3-540-45220-1_6","volume-title":"Computer Science Logic","author":"F. Boerner","year":"2003","unstructured":"Boerner, F., Bulatov, A., Krokhin, A., Jeavons, P.: Quantified constraints: Algorithms and complexity. In: Baaz, M., Makowsky, J.A. (eds.) CSL 2003. LNCS, vol.\u00a02803, pp. 58\u201370. Springer, Heidelberg (2003)"},{"key":"13_CR6","unstructured":"Bulatov, A., Dalmau, V.: A simple algorithm for Mal\u2019tsev constraints. SIAM J. Comp. (to appear)"},{"key":"13_CR7","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":"13_CR8","doi-asserted-by":"crossref","unstructured":"Bulatov, A., Krokhin, A., Jeavons, P.: The complexity of maximal constraint languages. In: Proceedings of STOC 2001, pp. 667\u2013674 (2001)","DOI":"10.1145\/380752.380868"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: A dichotomy theorem for constraints on a three-element set. In: FOCS 2002, pp. 649\u2013658 (2002)","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"13_CR10","unstructured":"Chen, H.: The computational complexity of quantified constraint satisfaction. Ph.D. thesis, Cornell University (August 2004)"},{"key":"13_CR11","unstructured":"Chen, H.: Collapsibility and consistency in quantified constraint satisfaction. In: AAAI, pp. 155\u2013160 (2004)"},{"key":"13_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-540-31856-9_26","volume-title":"STACS 2005","author":"H. Chen","year":"2005","unstructured":"Chen, H.: Quantified constraint satisfaction, maximal constraint languages, and symmetric polymorphisms. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 315\u2013326. Springer, Heidelberg (2005)"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Dalmau, V.: Generalized majority-minority operations are tractable. In: LICS, pp. 438\u2013447 (2005)","DOI":"10.2168\/LMCS-2(4:1)2006"},{"key":"13_CR14","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":"13_CR15","unstructured":"Gottlob, G., Greco, G., Scarcello, F.: The complexity of quantified constraint satisfaction problems under structural restrictions. In: IJCAI 2005 (2005)"},{"key":"13_CR16","volume-title":"A shorter model theory","author":"W. Hodges","year":"1997","unstructured":"Hodges, W.: A shorter model theory. Cambridge University Press, Cambridge (1997)"},{"issue":"1-2","key":"13_CR17","first-page":"251","volume":"101","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P., Cohen, D., Cooper, M.: Constraints, consistency and closure. AI\u00a0101(1-2), 251\u2013265 (1998)","journal-title":"AI"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. In: Proceedings of PODS 1998, pp. 205\u2013213 (1998)","DOI":"10.1145\/275487.275511"},{"issue":"4","key":"13_CR19","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1147\/rd.254.0327","volume":"25","author":"D. Kozen","year":"1981","unstructured":"Kozen, D.: Positive first-order logic is NP-complete. IBM Journal of Research and Development\u00a025(4), 327\u2013332 (1981)","journal-title":"IBM Journal of Research and Development"},{"key":"13_CR20","unstructured":"Pan, G., Vardi, M.: Fixed-parameter hierarchies inside PSPACE. In: LICS 2006 (to appear, 2006)"},{"key":"13_CR21","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meye, A.R.: Word problems requiring exponential time: Preliminary report. In: STOC, pp. 1\u20139 (1973)","DOI":"10.1145\/800125.804029"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11874683_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,8]],"date-time":"2023-05-08T20:21:37Z","timestamp":1683577297000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11874683_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540454588","9783540454595"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11874683_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}