{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T15:31:40Z","timestamp":1774798300784,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540705826","type":"print"},{"value":"9783540705833","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70583-3_17","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"197-208","source":"Crossref","is-referenced-by-count":3,"title":["Quantified Constraint Satisfaction and the Polynomially Generated Powers Property"],"prefix":"10.1007","author":[{"given":"Hubie","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"17_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"},{"key":"17_CR2","unstructured":"Berman, J., Idziak, P., Markovic, P., McKenzie, R., Valeriote, M., Willard, R.: Varieties with few subalgebras of powers (submitted for publication)"},{"key":"17_CR3","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"},{"issue":"1","key":"17_CR4","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1137\/050628957","volume":"36","author":"A. Bulatov","year":"2006","unstructured":"Bulatov, A., Dalmau, V.: A simple algorithm for mal\u2019tsev constraints. SIAM Journal of Computing\u00a036(1), 16\u201327 (2006)","journal-title":"SIAM Journal of Computing"},{"issue":"3","key":"17_CR5","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A. Bulatov","year":"2005","unstructured":"Bulatov, A., Jeavons, P., Krokhin, A.: Classifying the complexity of constraints using finite algebras. SIAM J. Computing\u00a034(3), 720\u2013742 (2005)","journal-title":"SIAM J. Computing"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. Journal of the ACM (J. ACM)\u00a053 (2006)","DOI":"10.1145\/1120582.1120584"},{"issue":"1","key":"17_CR7","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":"17_CR8","unstructured":"Chen, H.: The computational complexity of quantiifed constraint satisfaction. Ph.D. thesis, Cornell University (August 2004)"},{"key":"17_CR9","unstructured":"Chen, H.: Quantified constraint satisfaction and bounded treewidth. In: ECAI (2004)"},{"issue":"4","key":"17_CR10","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s10472-005-7031-4","volume":"44","author":"H. Chen","year":"2005","unstructured":"Chen, H.: The expressive rate of constraints. Annals of Mathematics and Artificial Intelligence\u00a044(4), 341\u2013352 (2005)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Chen, H.: A rendezvous of logic, complexity, and algebra. SIGACT News Logic Column (December 2006)","DOI":"10.1145\/1189056.1189076"},{"issue":"5","key":"17_CR12","doi-asserted-by":"publisher","first-page":"1674","DOI":"10.1137\/060668572","volume":"37","author":"H. Chen","year":"2008","unstructured":"Chen, H.: The complexity of quantified constraint satisfaction: Collapsibility, sink algebras, and the three-element case. SIAM Journal on Computing\u00a037(5), 1674\u20131701 (2008)","journal-title":"SIAM Journal on Computing"},{"key":"17_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11538363_17","volume-title":"Computer Science Logic","author":"H. Chen","year":"2005","unstructured":"Chen, H., Dalmau, V.: From pebble games to tractability: An ambidextrous consistency algorithm for quantified constraint satisfaction. In: Ong, L. (ed.) CSL 2005. LNCS, vol.\u00a03634, Springer, Heidelberg (2005)"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classification of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (2001)","DOI":"10.1137\/1.9780898718546"},{"key":"17_CR15","unstructured":"Dalmau, V.: Computational complexity of problems over generalized formulas. Ph.D. Thesis, UPC"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"Dalmau, V.: Generalized majority-minority operations are tractable. In: LICS (2005)","DOI":"10.2168\/LMCS-2(4:1)2006"},{"key":"17_CR17","volume-title":"Mathematical Logic","author":"H.D. Ebbinghaus","year":"1984","unstructured":"Ebbinghaus, H.D., Flum, J., Thomas, W.: Mathematical Logic. Springer, Heidelberg (1984)"},{"key":"17_CR18","unstructured":"Gottlob, G., Greco, G., Scarcello, F.: The complexity of quantified constraint satisfaction problems under structural restrictions. In: IJCAI (2005)"},{"key":"17_CR19","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(92)90149-A","volume":"101","author":"E. Gr\u00e4del","year":"1992","unstructured":"Gr\u00e4del, E.: Capturing complexity classes by fragments of second order logic. Theoretical Computer Science\u00a0101, 35\u201357 (1992)","journal-title":"Theoretical Computer Science"},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"Idziak, P., Markovic, P., McKenzie, R., Valeriote, M., Willard, R.: Tractability and learnability arising from algebras with few subpowers (extended abstract). In: LICS (2007)","DOI":"10.1109\/LICS.2007.50"},{"key":"17_CR21","doi-asserted-by":"crossref","unstructured":"Karpinski, M., B\u00fcning, H.K., Schmitt, P.H.: On the computational complexity of quantified horn clauses. In: CSL 1987, pp. 129\u2013137 (1987)","DOI":"10.1007\/3-540-50241-6_34"},{"key":"17_CR22","doi-asserted-by":"crossref","unstructured":"Kiss, E., Valeriote, M.: On tractability and congruence distributivity. In: LICS (2006)","DOI":"10.1109\/LICS.2006.40"},{"key":"17_CR23","unstructured":"Pan, G., Vardi, M.Y.: Fixed-parameter hierarchies inside pspace. In: LICS (2006)"},{"key":"17_CR24","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","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70583-3_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:07:56Z","timestamp":1605762476000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70583-3_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540705826","9783540705833"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70583-3_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}