{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:57Z","timestamp":1760202597836},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540249986"},{"type":"electronic","value":"9783540318569"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-31856-9_26","type":"book-chapter","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T18:06:19Z","timestamp":1267553179000},"page":"315-326","source":"Crossref","is-referenced-by-count":7,"title":["Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms"],"prefix":"10.1007","author":[{"given":"Hubie","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"26_CR1","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters\u00a08(3), 121\u2013123 (1979)","journal-title":"Information Processing Letters"},{"issue":"1","key":"26_CR2","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/970831.970840","volume":"35","author":"E. B\u00f6hler","year":"2004","unstructured":"B\u00f6hler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with boolean blocks, part II: constraint satisfaction problems. ACM SIGACT-Newsletter\u00a035(1), 22\u201335 (2004)","journal-title":"ACM SIGACT-Newsletter"},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"B\u00f6rner, F., Bulatov, A., Krokhin, A., Jeavons, P.: Quantified constraints: Algorithms and complexity. In: Computer Science Logic 2003 (2003)","DOI":"10.1007\/978-3-540-45220-1_6"},{"key":"26_CR4","unstructured":"Bulatov, A.: Combinatorial problems raised from 2-semilattices (manuscript)"},{"key":"26_CR5","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":"26_CR6","unstructured":"Bulatov, A.: Malt\u2019sev constraints are tractable. Technical Report PRG-RR-02-05, Oxford University (2002)"},{"key":"26_CR7","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\u2013330 (2003)","DOI":"10.1109\/LICS.2003.1210072"},{"key":"26_CR8","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":"26_CR9","unstructured":"Bulatov, A., Jeavons, P.: Tractable constraints closed under a binary operation. Technical Report PRG-TR-12-00, Oxford University (2000)"},{"key":"26_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/3-540-45022-X_24","volume-title":"Automata, Languages and Programming","author":"A. Bulatov","year":"2000","unstructured":"Bulatov, A., Krokhin, A., Jeavons, P.: Constraint satisfaction problems and finite algebras. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 272\u2013282. Springer, Heidelberg (2000)"},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"Bulatov, A., Krokhin, A., Jeavons, P.: The complexity of maximal constraint languages. In: ACM Symposium on Theory of Computing, pp. 667\u2013674 (2001)","DOI":"10.1145\/380752.380868"},{"issue":"1","key":"26_CR12","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1006\/inco.1995.1025","volume":"117","author":"H.K. B\u00fcning","year":"1995","unstructured":"B\u00fcning, H.K., Karpinski, M., Fl\u00f6gel, A.: Resolution for quantified boolean formulas. Information and Computation\u00a0117(1), 12\u201318 (1995)","journal-title":"Information and Computation"},{"key":"26_CR13","unstructured":"Chen, H.: Collapsibility and consistency in quantified constraint satisfaction. In: AAAI (2004)"},{"key":"26_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/978-3-540-30201-8_15","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2004","author":"H. Chen","year":"2004","unstructured":"Chen, H.: Quantified constraint satisfaction and 2-semilattice polymorphisms. In: Wallace, M. (ed.) CP 2004. LNCS, vol.\u00a03258, pp. 168\u2013181. Springer, Heidelberg (2004)"},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classification of Boolean Constraint Satisfaction Problems, Society for Industrial and Applied Mathematics. SIAM Monographs on Discrete Mathematics and Applications (2001)","DOI":"10.1137\/1.9780898718546"},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"Dalmau, V.: Some dichotomy theorems on constant-free quantified boolean formulas. Technical Report LSI-97-43-R, Llenguatges i Sistemes Inform\u00e0tics - Universitat Polit\u00e8cnica de Catalunya (1997)","DOI":"10.1145\/267460.267496"},{"key":"26_CR17","unstructured":"Dalmau, V.: A new tractable class of constraint satisfaction problems. In: 6th International Symposium on Artificial Intelligence and Mathematics (2000)"},{"key":"26_CR18","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)"},{"issue":"1","key":"26_CR19","doi-asserted-by":"publisher","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.\u00a028(1), 57\u2013104 (1998)","journal-title":"SIAM J. Comput."},{"key":"26_CR20","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P.: On the algebraic structure of combinatorial problems. Theoretical Computer Science\u00a0200, 185\u2013204 (1998)","journal-title":"Theoretical Computer Science"},{"issue":"1-2","key":"26_CR21","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-4","key":"26_CR22","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1023\/A:1018941030227","volume":"24","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P., Cohen, D., Pearson, J.: Constraints and universal algebra. Annals of Mathematics and Artificial Intelligence\u00a024(1-4), 51\u201367 (1998)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"26_CR23","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P.G. Jeavons","year":"1997","unstructured":"Jeavons, P.G., Cohen, D.A., Gyssens, M.: Closure properties of constraints. Journal of the ACM\u00a044, 527\u2013548 (1997)","journal-title":"Journal of the ACM"},{"issue":"1","key":"26_CR24","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1137\/S0097539795285114","volume":"28","author":"D. Kavvadias","year":"1998","unstructured":"Kavvadias, D., Sideri, M.: The inverse satisfiability problem. SIAM Journal on Computing\u00a028(1), 152\u2013163 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"26_CR25","doi-asserted-by":"publisher","first-page":"1863","DOI":"10.1137\/S0097539799349948","volume":"30","author":"S. Khanna","year":"2001","unstructured":"Khanna, S., Sudan, M., Trevisan, L., Williamson, D.P.: The approximability of constraint satisfaction problems. SIAM Journal on Computing\u00a030(6), 1863\u20131920 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"26_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/3-540-44693-1_36","volume-title":"STACS 2001","author":"L.M. Kirousis","year":"2001","unstructured":"Kirousis, L.M., Kolaitis, P.G.: The complexity of minimal satisfiability problems. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 407\u2013418. Springer, Heidelberg (2001)"},{"key":"26_CR27","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"P..G. Kolaitis","year":"2000","unstructured":"Kolaitis, Ph.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":"26_CR28","volume-title":"The Two-Valued Iterative Systems of Mathematical Logic","author":"E.L. Post","year":"1941","unstructured":"Post, E.L.: The Two-Valued Iterative Systems of Mathematical Logic. Princeton University Press, Princeton (1941)"},{"key":"26_CR29","series-title":"Colloq. Math. Soc. Janos Bolyai","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/B978-0-444-87759-8.50029-8","volume-title":"Lectures in Universal Algebra (Proc. Conf. Szeged 1983)","author":"I.G. Rosenberg","year":"1986","unstructured":"Rosenberg, I.G.: Minimal clones I: the five types. In: Lectures in Universal Algebra (Proc. Conf. Szeged 1983). Colloq. Math. Soc. Janos Bolyai, vol.\u00a043, pp. 405\u2013427. North-Holland, Amsterdam (1986)"},{"key":"26_CR30","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","STACS 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-31856-9_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:29:46Z","timestamp":1605760186000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-31856-9_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540249986","9783540318569"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-31856-9_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}