{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:01:08Z","timestamp":1725858068875},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319401881"},{"type":"electronic","value":"9783319401898"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-40189-8_34","type":"book-chapter","created":{"date-parts":[[2016,6,13]],"date-time":"2016-06-13T15:34:07Z","timestamp":1465832047000},"page":"333-342","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Counting Quantifiers on Equality Languages"],"prefix":"10.1007","author":[{"given":"Barnaby","family":"Martin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e1s","family":"Pongr\u00e1cz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Wrona","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,6,14]]},"reference":[{"issue":"3","key":"34_CR1","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"DAM Barrington","year":"1990","unstructured":"Barrington, D.A.M., Immerman, N., Straubing, H.: On uniformity within NC $$^1$$ 1 . J. Comput. Syst. Sci. 41(3), 274\u2013306 (1990)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"34_CR2","doi-asserted-by":"crossref","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 J. Comput. 38(5), 1782\u20131802 (2009)","journal-title":"SIAM J. Comput."},{"key":"34_CR3","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Chen, H.: Quantified equality constraints. In: Proceedings of LICS 2007, pp. 203\u2013212 (2007)","DOI":"10.1109\/LICS.2007.38"},{"issue":"8","key":"34_CR4","doi-asserted-by":"crossref","first-page":"3682","DOI":"10.1137\/080725209","volume":"39","author":"M Bodirsky","year":"2010","unstructured":"Bodirsky, M., Chen, H.: Quantified equality constraints. SIAM J. Comput. 39(8), 3682\u20133699 (2010)","journal-title":"SIAM J. Comput."},{"key":"34_CR5","unstructured":"Bodirsky, M., Chen, H.: Personal communication (2012)"},{"issue":"4","key":"34_CR6","doi-asserted-by":"crossref","first-page":"1249","DOI":"10.2178\/jsl\/1286198146","volume":"75","author":"M Bodirsky","year":"2010","unstructured":"Bodirsky, M., Chen, H., Pinsker, M.: The reducts of equality up to primitive positive interdefinability. J. Symb. Log. 75(4), 1249\u20131292 (2010)","journal-title":"J. Symb. Log."},{"issue":"2","key":"34_CR7","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1007\/s00224-007-9083-9","volume":"43","author":"M Bodirsky","year":"2008","unstructured":"Bodirsky, M., K\u00e1ra, J.: The complexity of equality constraint languages. Theor. Comput. Syst. 43(2), 136\u2013158 (2008). A preliminary version appeared in the proceedings of CSR 2006","journal-title":"Theor. Comput. Syst."},{"issue":"1","key":"34_CR8","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"},{"issue":"3","key":"34_CR9","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"AA Bulatov","year":"2005","unstructured":"Bulatov, A.A., Jeavons, P., Krokhin, A.A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34(3), 720\u2013742 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"34_CR10","doi-asserted-by":"crossref","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 26(1), 51\u201362 (2007)","journal-title":"Topoi"},{"key":"34_CR11","volume-title":"Finite Model Theory","author":"H-D Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1999)","edition":"2"},{"key":"34_CR12","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1999","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP, constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput. 28, 57\u2013104 (1999). A preliminary version appeared in the proceedings of STOC 1993","journal-title":"SIAM J. Comput."},{"issue":"1","key":"34_CR13","doi-asserted-by":"crossref","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. J. Comb. Theor. Ser. B 48(1), 92\u2013110 (1990)","journal-title":"J. Comb. Theor. Ser. B"},{"key":"34_CR14","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Finite Model Theory and Its Applications","author":"PG Kolaitis","year":"2005","unstructured":"Kolaitis, P.G., Vardi, M.Y.: A logical Approach to Constraint Satisfaction. In: Creignou, N., Kolaitis, P.G., Vollmer, H. (eds.) Finite Model Theory and Its Applications. Texts in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2005)"},{"issue":"2","key":"34_CR15","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1137\/140981332","volume":"29","author":"B Martin","year":"2015","unstructured":"Martin, B., Madelaine, F.R., Stacho, J.: Constraint satisfaction with counting quantifiers. SIAM J. Discrete Math. 29(2), 1065\u20131113 (2015). Extended abstracts appeared at CSR 2012 and CSR 2014","journal-title":"SIAM J. Discrete Math."},{"key":"34_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-21676-7","volume-title":"Bounded Variable Logics and Counting - A Study in Finite Models","author":"M Otto","year":"1997","unstructured":"Otto, M.: Bounded Variable Logics and Counting - A Study in Finite Models, vol. 9. Springer, Heidelberg (1997). IX+183pp"},{"key":"34_CR17","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"},{"key":"34_CR18","unstructured":"Schmidt, J., Wrona, M.: The complexity of abduction for equality constraint languages. In: Computer Science Logic (CSL 2013), pp. 615\u2013633 (2013)"},{"key":"34_CR19","series-title":"Studies in Linguistics and Philosophy","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-28749-2","volume-title":"Quantifiers and Cognition: Logical and Computational Perspectives","author":"J Szymanik","year":"2016","unstructured":"Szymanik, J.: Quantifiers and Cognition: Logical and Computational Perspectives. Studies in Linguistics and Philosophy. Springer, Cham (2016)"}],"container-title":["Lecture Notes in Computer Science","Pursuit of the Universal"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-40189-8_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T16:17:31Z","timestamp":1498321051000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-40189-8_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319401881","9783319401898"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-40189-8_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}