{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:00Z","timestamp":1760202600843},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540408017"},{"type":"electronic","value":"9783540452201"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45220-1_6","type":"book-chapter","created":{"date-parts":[[2010,6,25]],"date-time":"2010-06-25T19:33:58Z","timestamp":1277494438000},"page":"58-70","source":"Crossref","is-referenced-by-count":27,"title":["Quantified Constraints: Algorithms and Complexity"],"prefix":"10.1007","author":[{"given":"Ferdinand","family":"B\u00f6rner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrei","family":"Bulatov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Jeavons","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrei","family":"Krokhin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_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., Tarjan, R.: A linear time algorithm for testing the truth of certain quantified Boolean formulas. Information Processing Letters\u00a08, 121\u2013123 (1979)","journal-title":"Information Processing Letters"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/3-540-45793-3_28","volume-title":"Computer Science Logic","author":"E. B\u00f6hler","year":"2002","unstructured":"B\u00f6hler, E., Hemaspaandra, E., Reith, S., Vollmer, H.: Equivalence and isomorphism for Boolean constraint satisfaction. In: Bradfield, J.C. (ed.) CSL 2002 and EACSL 2002. LNCS, vol.\u00a02471, pp. 412\u2013426. Springer, Heidelberg (2002)"},{"key":"6_CR3","unstructured":"B\u00f6rner, F., Krokhin, A., Bulatov, A., Jeavons, P.: Quantified constraints and surjective polymorphisms. Technical Report PRG-RR-02-11, Computing Laboratory, University of Oxford, UK (2002)"},{"key":"6_CR4","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, FOCS 2002, pp. 649\u2013658 (2002)","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"6_CR5","unstructured":"Bulatov, A.: Mal\u2019tsev constraints are tractable. Technical Report RR-02-05, Computing Laboratory, Oxford University (2002)"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: Tractable conservative constraint satisfaction problems. In: Proceedings 18th IEEE Symposium on Logic in Computer Science, LICS 2003 (2003) (to appear)","DOI":"10.1109\/LICS.2003.1210072"},{"key":"6_CR7","unstructured":"Bulatov, A., Jeavons, P.: Algebraic structures in combinatorial problems. Technical Report MATH-AL-4-2001, Technische Universit\u00e4t Dresden, Germany (2001)"},{"key":"6_CR8","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":"6_CR9","doi-asserted-by":"crossref","unstructured":"Bulatov, A., Krokhin, A., Jeavons, P.: The complexity of maximal constraint languages. In: Proceedings 33rd ACM Symposium on Theory of Computing, STOC 2001, pp. 667\u2013674 (2001)","DOI":"10.1145\/380752.380868"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/0004-3702(94)90021-3","volume":"65","author":"M. Cooper","year":"1994","unstructured":"Cooper, M., Cohen, D., Jeavons, P.: Characterising tractable constraints. Artificial Intelligence\u00a065, 347\u2013361 (1994)","journal-title":"Artificial Intelligence"},{"key":"6_CR11","unstructured":"Creignou, N., Daud\u00e9, H.: Random generalized satisfiability problems. In: Proceedings of 5th International Symposium on Theory and Applications of Satisfiability Testing - SAT 2002, pp. 17\u201326 (2002)"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications, vol.\u00a07 (2001)","DOI":"10.1137\/1.9780898718546"},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/S0304-3975(01)00146-3","volume":"288","author":"P. Crescenzi","year":"2002","unstructured":"Crescenzi, P., Rossi, G.: On the Hamming distance of constraint satisfaction problems. Theoretical Computer Science\u00a0288, 85\u2013100 (2002)","journal-title":"Theoretical Computer Science"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Dalmau, V.: Some dichotomy theorems on constant-free quantified Boolean formulas. Technical Report TR LSI-97-43-R, Department LSI, Universitat Politecnica de Catalunya (1997)","DOI":"10.1145\/267460.267496"},{"key":"6_CR15","unstructured":"Dalmau, V.: A new tractable class of constraint satisfaction problems. In: Proceedings 6th International Symposium on Artificial Intelligence and Mathematics (2000)"},{"key":"6_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1007\/3-540-45465-9_36","volume-title":"Automata, Languages and Programming","author":"V. Dalmau","year":"2002","unstructured":"Dalmau, V.: Constraint satisfaction problems in non-deterministic logarithmic space. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 414\u2013425. Springer, Heidelberg (2002)"},{"key":"6_CR17","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1998","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 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"6_CR18","series-title":"NATO ASI Series","volume-title":"Constraint Programming","author":"E. Freuder","year":"1993","unstructured":"Freuder, E.: Exploiting structure in constraint satisfaction problems. In: Mayoh, M., Tyugum, E., Penjam, J. (eds.) Constraint Programming. NATO ASI Series, vol.\u00a0131, Springer, Heidelberg (1993)"},{"key":"6_CR19","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"6_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"},{"key":"6_CR21","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P. Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: Closure properties of constraints. Journal of the ACM\u00a044, 527\u2013548 (1997)","journal-title":"Journal of the ACM"},{"key":"6_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/3-540-48321-7_27","volume-title":"Fundamentals of Computation Theory","author":"L. Juban","year":"1999","unstructured":"Juban, L.: Dichotomy theorem for generalized unique satisfiability problem. In: Ciobanu, G., P\u0103un, G. (eds.) FCT 1999. LNCS, vol.\u00a01684, pp. 327\u2013337. Springer, Heidelberg (1999)"},{"key":"6_CR23","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1137\/S0097539795285114","volume":"28","author":"D. Kavvadias","year":"1998","unstructured":"Kavvadias, D., Sireni, M.: The inverse satisfiability problem. SIAM Journal on Computing\u00a028, 152\u2013163 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"6_CR24","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0004-3702(93)90063-H","volume":"64","author":"L. Kirousis","year":"1993","unstructured":"Kirousis, L.: Fast parallel constraint satisfaction. Artificial Intelligence\u00a064, 147\u2013160 (1993)","journal-title":"Artificial Intelligence"},{"key":"6_CR25","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. Kirousis","year":"2001","unstructured":"Kirousis, L., Kolaitis, P.: The complexity of minimal satisfiability problems. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 407\u2013418. Springer, Heidelberg (2001)"},{"key":"6_CR26","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1006\/inco.1995.1025","volume":"117","author":"H. Kleine B\u00fcning","year":"1995","unstructured":"Kleine B\u00fcning, H., Karpinski, M., Fl\u00f6gel, A.: Resolution for quantified Boolean formulas. Information and Computation\u00a0117, 12\u201318 (1995)","journal-title":"Information and Computation"},{"key":"6_CR27","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"P. Kolaitis","year":"2000","unstructured":"Kolaitis, P., Vardi, M.: 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":"6_CR28","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/5625.001.0001","volume-title":"Programming with Constraints: an Introduction","author":"K. Marriott","year":"1998","unstructured":"Marriott, K., Stuckey, P.: Programming with Constraints: an Introduction. MIT Press, Cambridge (1998)"},{"key":"6_CR29","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"6_CR30","volume-title":"Theories of Computability","author":"N. Pippenger","year":"1997","unstructured":"Pippenger, N.: Theories of Computability. Cambridge University Press, Cambridge (1997)"},{"key":"6_CR31","unstructured":"P\u00f6schel, R.: Galois connections for operations and relations. Technical Report MATH-AL-8-2001, Technische Universit\u00e4t Dresden, Germany (2001)"},{"key":"6_CR32","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1007\/978-3-0348-5547-1_5","volume-title":"Funktionen- und Relationenalgebren","author":"Reinhard P\u00f6schel","year":"1979","unstructured":"P\u00f6schel, R., Kalu\u017enin, L.: Funktionen- und Relationenalgebren. DVW, Berlin (1979)"},{"key":"6_CR33","series-title":"Annals Mathematical Studies","volume-title":"The two-valued iterative systems of mathematical logic","author":"E. Post","year":"1941","unstructured":"Post, E.: The two-valued iterative systems of mathematical logic. Annals Mathematical Studies, vol.\u00a05. Princeton University Press, Princeton (1941)"},{"key":"6_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1007\/3-540-44612-5_59","volume-title":"Mathematical Foundations of Computer Science 2000","author":"S. Reith","year":"2000","unstructured":"Reith, S., Vollmer, H.: Optimal satisfiability for propositional calculi and constraint satisfaction problems. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol.\u00a01893, pp. 640\u2013649. Springer, Heidelberg (2000)"},{"key":"6_CR35","doi-asserted-by":"crossref","unstructured":"Schaefer, T.: The complexity of satisfiability problems. In: Proceedings 10th ACM Symposium on Theory of Computing, STOC 1978, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"6_CR36","unstructured":"Szendrei, A.: Clones in Universal Algebra. Seminaires de Mathematiques Superieures, vol.\u00a099. University of Montreal (1986)"},{"key":"6_CR37","volume-title":"Foundations of Constraint Satisfaction","author":"E. Tsang","year":"1993","unstructured":"Tsang, E.: Foundations of Constraint Satisfaction. Academic Press, London (1993)"},{"key":"6_CR38","unstructured":"Williams, R.: Algorithms for quantified Boolean formulas. In: Proceedings ACM Symposium on Discrete Algorithms, SODA 2002, pp. 299\u2013307 (2002)"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45220-1_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T09:01:51Z","timestamp":1559206911000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45220-1_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540408017","9783540452201"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45220-1_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}