{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:05:32Z","timestamp":1725566732026},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540282310"},{"type":"electronic","value":"9783540318972"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11538363_17","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T13:35:33Z","timestamp":1127828133000},"page":"232-247","source":"Crossref","is-referenced-by-count":14,"title":["From Pebble Games to Tractability: An Ambidextrous Consistency Algorithm for Quantified Constraint Satisfaction"],"prefix":"10.1007","author":[{"given":"Hubie","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V\u00edctor","family":"Dalmau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"17_CR1","unstructured":"Bulatov, A.: Combinatorial problems raised from 2-semilattices (Manuscript)"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: A dichotomy theorem for constraints on a three-element set. In: Proceedings of 43rd IEEE Symposium on Foundations of Computer Science, pp. 649\u2013658 (2002)","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"#cr-split#-17_CR3.1","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: Tractable conservative constraint satisfaction problems. In: Proceedings of 18th IEEE Symposium on Logic in Computer Science (LICS 2003), pp. 321???330 (2003);","DOI":"10.1109\/LICS.2003.1210072"},{"key":"#cr-split#-17_CR3.2","unstructured":"Extended version appears as Oxford University technical report PRG-RR???03-01"},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: A graph of a relational structure and constraint satisfaction problems. In: Proceedings of 19th IEEE Annual Symposium on Logic in Computer Science, LICS 2004 (2004)","DOI":"10.1109\/LICS.2004.1319639"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"Chandra, A., Merlin, P.: Optimal implementation of conjunctive queries in relational data bases. In: STOC (1977)","DOI":"10.1145\/800105.803397"},{"key":"17_CR6","unstructured":"Chen, H.: The Computational Complexity of Quantified Constraint Satisfaction. PhD thesis, Cornell University (August 2004)"},{"key":"17_CR7","unstructured":"Chen, H.: Quantified constraint satisfaction and bounded treewidth. In: ECAI (2004)"},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"Chen, H.: Quantified constraint satisfaction, maximal constraint languages, and symmetric polymorphisms. In: STACS (2005)","DOI":"10.1007\/978-3-540-31856-9_26"},{"key":"17_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/3-540-46135-3_21","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"V. Dalmau","year":"2002","unstructured":"Dalmau, V., Kolaitis, P.G., Vardi, M.Y.: Constraint satisfaction, bounded treewidth, and finite-variable logics. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, p. 310. Springer, Heidelberg (2002)"},{"key":"17_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/978-3-540-48085-3_12","volume-title":"Principles and Practice of Constraint Programming \u2013 CP\u201999","author":"V. Dalmau","year":"1999","unstructured":"Dalmau, V., Pearson, J.: Closure functions and width 1 problems. In: Jaffar, J. (ed.) CP 1999. LNCS, vol.\u00a01713, pp. 159\u2013173. Springer, Heidelberg (1999)"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Dechter, R., Pearl, J.: Tree clustering for constraint networks. Artificial Intelligence, pp. 353\u2013366 (1989)","DOI":"10.1016\/0004-3702(89)90037-4"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"Flum, J., Frick, M., Grohe, M.: Query evaluation via tree-decompositions. JACM (2002)","DOI":"10.1145\/602220.602222"},{"key":"17_CR13","unstructured":"Freuder, E.: Complexity of k-tree structured constraint satisfaction problems. In: AAAI 1990 (1990)"},{"key":"17_CR14","unstructured":"Gottlob, G., Greco, G., Scarcello, F.: The complexity of quantified constraint satisfaction problems under structural restrictions. In: IJCAI (2005)"},{"issue":"2","key":"17_CR15","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0004-3702(00)00078-3","volume":"124","author":"G. Gottlob","year":"2000","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: A comparison of structural csp decomposition methods. Artif. Intell.\u00a0124(2), 243\u2013282 (2000)","journal-title":"Artif. Intell."},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. In: FOCS 2003, pp. 552\u2013561 (2003)","DOI":"10.1109\/SFCS.2003.1238228"},{"issue":"1-2","key":"17_CR17","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0004-3702(98)00022-8","volume":"101","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P., Cohen, D., Cooper, M.: Constraints, consistency, and closure. Articial Intelligence\u00a0101(1-2), 251\u2013265 (1998)","journal-title":"Articial Intelligence"},{"issue":"1","key":"17_CR18","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1006\/jcss.1995.1055","volume":"51","author":"P.G. Kolaitis","year":"1995","unstructured":"Kolaitis, P.G., Vardi, M.Y.: On the expressive power of Datalog: tools and a case study. Journal of Computer and System Sciences\u00a051(1), 110\u2013134 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"17_CR19","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"P.G. Kolaitis","year":"2000","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences\u00a061, 302\u2013332 (2000)","journal-title":"Journal of Computer and System Sciences"},{"key":"17_CR20","unstructured":"Kolaitis, P.G., Vardi, M.Y.: A game-theoretic approach to constraint satisfaction. In: Proceedings 17th National (US) Conference on Artificial Intellignece, AAAI 2000, pp. 175\u2013181 (2000)"},{"key":"17_CR21","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11538363_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:54:12Z","timestamp":1619506452000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11538363_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540282310","9783540318972"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11538363_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}