{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,6]],"date-time":"2025-04-06T20:40:08Z","timestamp":1743972008680,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642306419"},{"type":"electronic","value":"9783642306426"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-30642-6_24","type":"book-chapter","created":{"date-parts":[[2012,8,11]],"date-time":"2012-08-11T08:01:39Z","timestamp":1344672099000},"page":"253-265","source":"Crossref","is-referenced-by-count":4,"title":["Constraint Satisfaction with Counting Quantifiers"],"prefix":"10.1007","author":[{"given":"Florent","family":"Madelaine","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Barnaby","family":"Martin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juraj","family":"Stacho","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"24_CR1","doi-asserted-by":"publisher","first-page":"1782","DOI":"10.1137\/070708093","volume":"38","author":"L. Barto","year":"2009","unstructured":"Barto, L., Kozik, M., Niven, T.: The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell). SIAM Journal on Computing\u00a038(5), 1782\u20131802 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"24_CR2","unstructured":"Bodirsky, M., K\u00e1ra, J., Martin, B.: The complexity of surjective homomorphism problems \u2013 a survey. CoRR abs\/1104.5257 (2011)"},{"issue":"9","key":"24_CR3","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1016\/j.ic.2009.05.003","volume":"207","author":"F. B\u00f6rner","year":"2009","unstructured":"B\u00f6rner, F., Bulatov, A.A., Chen, H., Jeavons, P., Krokhin, A.A.: The complexity of constraint satisfaction games and qcsp. Inf. Comput.\u00a0207(9), 923\u2013944 (2009)","journal-title":"Inf. Comput."},{"key":"24_CR4","unstructured":"B\u00f6rner, F., Krokhin, A., Bulatov, A., Jeavons, P.: Quantified constraints and surjective polymorphisms. Tech. Rep. PRG-RR-02-11, Oxford University (2002)"},{"issue":"1","key":"24_CR5","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"A. Bulatov","year":"2006","unstructured":"Bulatov, A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM 53(1), 66\u2013120 (2006)","journal-title":"J. ACM"},{"key":"24_CR6","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A. Bulatov","year":"2005","unstructured":"Bulatov, A., Krokhin, A., Jeavons, P.G.: Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing\u00a034, 720\u2013742 (2005)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"24_CR7","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 J. Comput.\u00a037(5), 1674\u20131701 (2008)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"24_CR8","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1016\/j.ic.2008.11.001","volume":"207","author":"H. Chen","year":"2009","unstructured":"Chen, H.: Existentially restricted quantified constraint satisfaction. Inf. Comput.\u00a0207(3), 369\u2013388 (2009)","journal-title":"Inf. Comput."},{"key":"24_CR9","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/s00012-011-0125-4","volume":"65","author":"H. Chen","year":"2011","unstructured":"Chen, H.: Quantified Constraint Satisfaction and the Polynomially Generated Powers Property. Algebra Universalis\u00a065, 213\u2013241 (2011)","journal-title":"Algebra Universalis"},{"issue":"1","key":"24_CR10","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s11245-006-9008-2","volume":"26","author":"R. Clark","year":"2007","unstructured":"Clark, R., Grossman, M.: Number sense and quantifier interpretation. Topoi\u00a026(1), 51\u201362 (2007)","journal-title":"Topoi"},{"key":"24_CR11","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Springer (1999)"},{"issue":"2","key":"24_CR12","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jctb.1997.1812","volume":"72","author":"T. Feder","year":"1998","unstructured":"Feder, T., Hell, P.: List homomorphisms to reflexive graphs. J. Comb. Theory, Ser. B\u00a072(2), 236\u2013250 (1998)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"4","key":"24_CR13","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s004939970003","volume":"19","author":"T. Feder","year":"1999","unstructured":"Feder, T., Hell, P., Huang, J.: List homomorphisms and circular arc graphs. Combinatorica\u00a019(4), 487\u2013505 (1999)","journal-title":"Combinatorica"},{"issue":"1","key":"24_CR14","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1137\/080738866","volume":"24","author":"T. Feder","year":"2010","unstructured":"Feder, T., Hell, P., Jonsson, P., Krokhin, A.A., Nordh, G.: Retractions to pseudoforests. SIAM J. Discrete Math.\u00a024(1), 101\u2013112 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"24_CR15","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1999","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 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"24_CR16","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-coloring. Journal of Combinatorial Theory, Series B\u00a048, 92\u2013110 (1990)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"24_CR17","unstructured":"Hemaspaandra, E.: Dichotomy theorems for alternation-bounded quantified boolean formulas. CoRR cs.CC\/0406006 (2004)"},{"key":"24_CR18","unstructured":"Kolaitis, P.G., Vardi, M.Y.: A logical Approach to Constraint Satisfaction. In: Finite Model Theory and Its Applications (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag New York, Inc. (2005)"},{"key":"24_CR19","doi-asserted-by":"crossref","unstructured":"Lange, K.-J.: Some results on majority quantifiers over words. In: Proceedings of 19th IEEE Annual Conference on Computational Complexity, pp. 123\u2013129 (June 2004)","DOI":"10.1109\/CCC.2004.1313817"},{"key":"24_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/978-3-540-69407-6_45","volume-title":"Logic and Theory of Algorithms","author":"B. Martin","year":"2008","unstructured":"Martin, B.: First-Order Model Checking Problems Parameterized by the Model. In: Beckmann, A., Dimitracopoulos, C., L\u00f6we, B. (eds.) CiE 2008. LNCS, vol.\u00a05028, pp. 417\u2013427. Springer, Heidelberg (2008)"},{"key":"24_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/11780342_36","volume-title":"Logical Approaches to Computational Barriers","author":"B. Martin","year":"2006","unstructured":"Martin, B., Madelaine, F.: Towards a Trichotomy for Quantified H-Coloring. In: Beckmann, A., Berger, U., L\u00f6we, B., Tucker, J.V. (eds.) CiE 2006. LNCS, vol.\u00a03988, pp. 342\u2013352. Springer, Heidelberg (2006)"},{"key":"24_CR22","doi-asserted-by":"crossref","unstructured":"Otto, M.: Bounded variable logics and counting \u2013 A study in finite models, vol.\u00a09, IX+183 pages. Springer (1997)","DOI":"10.1007\/978-3-662-21676-7"},{"key":"24_CR23","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley (1994)"},{"issue":"4","key":"24_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O. Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM\u00a055(4), 1\u201324 (2008)","journal-title":"J. ACM"},{"key":"24_CR25","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of STOC 1978, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-30642-6_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,6]],"date-time":"2025-04-06T20:08:28Z","timestamp":1743970108000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-30642-6_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642306419","9783642306426"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-30642-6_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}