{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:08:53Z","timestamp":1760202533323},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540441205"},{"type":"electronic","value":"9783540461357"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-46135-3_25","type":"book-chapter","created":{"date-parts":[[2007,5,15]],"date-time":"2007-05-15T05:59:47Z","timestamp":1179208787000},"page":"371-386","source":"Crossref","is-referenced-by-count":37,"title":["Beyond NP: Arc-Consistency for Quantified Constraints"],"prefix":"10.1007","author":[{"given":"Lucas","family":"Bordeaux","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Monfroy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,9,2]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"K. Apt and E. Monfroy. Automatic generation of constraint propagation algorithms for small finite domains. In Proc. of the 5th Int. Conf. on Principles and Practice of Constraint Programming (CP), pages 58\u201372, Alexandria, Virginia, 1999. Springer.","DOI":"10.1007\/978-3-540-48085-3_5"},{"issue":"1\u20132","key":"25_CR2","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/S0304-3975(99)00032-8","volume":"221","author":"K. R. Apt","year":"1999","unstructured":"K. R. Apt. The essence of constraint propagation. Theoretical Computer Science, 221(1\u20132):179\u2013210, 1999.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"25_CR3","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0004-3702(96)00014-8","volume":"86","author":"J. L. Balc\u00e1zar","year":"1996","unstructured":"J. L. Balc\u00e1zar. The complexity of searching implicit graphs. Artificial Intelligence, 86(1):171\u2013188, 1996.","journal-title":"Artificial Intelligence"},{"key":"25_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/3-540-45349-0_7","volume-title":"Proc. of the 6th Int. Conf. on Principles and Practice of Constraint Programming (CP)","author":"F. Benhamou","year":"2000","unstructured":"F. Benhamou and F. Goualard. Universally quantified interval constraints. In Proc. of the 6th Int. Conf. on Principles and Practice of Constraint Programming (CP), LNCS, pages 67\u201382, Singapore, 2000. Springer."},{"issue":"1","key":"25_CR5","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1006\/inco.1995.1025","volume":"117","author":"H. K. Buening","year":"1995","unstructured":"H. K. Buening, M. Karpinski, and A. Flogel. Resolution for quantified boolean formulas. Information and Computation, 117(1):12\u201318, 1995.","journal-title":"Information and Computation"},{"issue":"1\u20132","key":"25_CR6","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0004-3702(94)90081-7","volume":"69","author":"T. Bylander","year":"1994","unstructured":"T. Bylander. The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69(1\u20132):165\u2013204, 1994.","journal-title":"Artificial Intelligence"},{"key":"25_CR7","unstructured":"M. Cadoli, A Giovanardi, and M. Schaerf. An algorithm to evaluate quantified boolean formulae. In Proc. of the 15th Nat. Conf. on AI (AAAI), pages 262\u2013267, Madison, USA, 1999. AAAI\/MIT Press."},{"issue":"3","key":"25_CR8","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0743-1066(95)00121-2","volume":"27","author":"P. Codognet","year":"1996","unstructured":"P. Codognet and D. Diaz. Compiling constraints in CLP(FD). J. of Logic Programming, 27(3):185\u2013226, 1996.","journal-title":"J. of Logic Programming"},{"key":"25_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1007\/3-540-45349-0_14","volume-title":"Proc. of the 6th Int. Conf. on Principles and Practice of Constraint Programming (CP)","author":"A. Colmerauer","year":"2000","unstructured":"A. Colmerauer and T. Dao. Expressiveness of full first order constraints in the algebra of finite or infinite trees. In Proc. of the 6th Int. Conf. on Principles and Practice of Constraint Programming (CP), LNCS, pages 172\u2013186, Singapore, 2000. Springer."},{"issue":"1","key":"25_CR10","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/S0304-3975(97)86737-0","volume":"173","author":"R. Dechter","year":"1997","unstructured":"R. Dechter and P. van Beek. Local and global relational consistency. Theoretical Computer Science, 173(1):283\u2013308, 1997.","journal-title":"Theoretical Computer Science"},{"key":"25_CR11","unstructured":"U. Egly, T. Eiter, H. Tompits, and S. Woltran. Solving advanced reasoning tasks using quantified boolean formulas. In Proc. of the 17th Nat. Conf. on AI (AAAI), pages 417\u2013422, Austin, TX, 2001. AAAI\/MIT Press."},{"issue":"1\u20133","key":"25_CR12","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/S0743-1066(98)10005-5","volume":"37","author":"T. W. Fruehwirth","year":"1998","unstructured":"T. W. Fruehwirth. Theory and practice of Constraint Handling Rules. J. of Logic Programming, 37(1\u20133):95\u2013138, 1998.","journal-title":"J. of Logic Programming"},{"key":"25_CR13","unstructured":"I. P. Gent and T. Walsh. Beyond NP: the QSAT phase transition. In Proc. of the 15th Nat. Conf. on AI (AAAI), pages 648\u2013653, Madison, USA, 1999. AAAI\/MIT Press."},{"key":"25_CR14","unstructured":"E. Giunchiglia, M. Narizzano, and A. Tacchella. Learning for quantified boolean logic satisfiability. In Proc. of the 18th Nat. Conf. on AI, Edmonton, Alberta, 2002. AAAI\/MIT Press. To appear."},{"issue":"3","key":"25_CR15","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1093\/logcom\/2.3.397","volume":"2","author":"G. Gottlob","year":"1992","unstructured":"G. Gottlob. Complexity results for nonmonotonic logics. J. of Logic and Computation, 2(3):397\u2013425, 1992.","journal-title":"J. of Logic and Computation"},{"key":"25_CR16","unstructured":"C. Papadimitriou. Computational Complexity. Addison Wesley, 1994."},{"key":"25_CR17","series-title":"Lect Notes Comput Sci","volume-title":"Artificial Intelligence, Automated Reasoning, and Symbolic Computation","author":"S. Ratschan","year":"2002","unstructured":"S. Ratschan. Continuous first-order constraint satisfaction. In Artificial Intelligence, Automated Reasoning, and Symbolic Computation, number 2385 in LNCS, Marseille, France, 2002. Springer."},{"key":"25_CR18","unstructured":"J. Rintanen. Improvements to the evaluation of quantified boolean formulae. In Proc. of the 16th Int. Joint Conf. on AI (IJCAI), pages 1192\u20131197, Stockholm, Sweden, 1999. Morgan Kaufmann."},{"issue":"2","key":"25_CR19","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0022-0000(78)90045-4","volume":"16","author":"T. J. Schaefer","year":"1978","unstructured":"T. J. Schaefer. Complexity of decision problems based on finite two-person perfect-information games. J. of Computer and System Sciences, 16(2):185\u2013225, 1978.","journal-title":"J. of Computer and System Sciences"},{"key":"25_CR20","doi-asserted-by":"crossref","unstructured":"L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time: Preliminary report. In Conf. Record of the 5th Symp. on the Theory of Computing (STOC), pages 1\u20139, Austin, TX, 1973. ACM.","DOI":"10.1145\/800125.804029"},{"key":"25_CR21","unstructured":"A. C. Ward, T. Lozano-Perez, and W. P. Seering. Extending the constraint propagation of intervals. In Proc. of the 11th Int. Joint Conf. on AI (IJCAI), pages 1453\u20131460, Detroit, Michigan, 1989. Morgan Kaufmann."}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming - CP 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46135-3_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T00:25:50Z","timestamp":1556411150000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46135-3_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441205","9783540461357"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-46135-3_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2002]]}}}