{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T08:59:54Z","timestamp":1790413194307,"version":"4.1.0"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319235332","type":"print"},{"value":"9783319235349","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-23534-9_11","type":"book-chapter","created":{"date-parts":[[2015,9,4]],"date-time":"2015-09-04T20:39:52Z","timestamp":1441399192000},"page":"193-209","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Is Polynomial Time Choiceless?"],"prefix":"10.1007","author":[{"given":"Erich","family":"Gr\u00e4del","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,9,5]]},"reference":[{"key":"11_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/978-3-662-44522-8_5","volume-title":"Mathematical Foundations of Computer Science 2014","author":"F Abu Zaid","year":"2014","unstructured":"Abu Zaid, F., Gr\u00e4del, E., Grohe, M., Pakusa, W.: Choiceless polynomial time on structures with small abelian colour classes. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014, Part I. LNCS, vol. 8634, pp. 50\u201362. Springer, Heidelberg (2014)"},{"key":"11_CR2","unstructured":"Anderson, M., Dawar, A.: On symmetric circuits and fixed-point logics. In: STACS, pp. 41\u201352 (2014)"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"1666","DOI":"10.1016\/j.tcs.2008.12.049","volume":"410","author":"A Atserias","year":"2009","unstructured":"Atserias, A., Bulatov, A., Dawar, A.: Affine systems of equations and counting infinitary logic. Theor. Comput. Sci. 410, 1666\u20131683 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Berkholz, C., Grohe, M.: Limitations of algebraic approaches to graph isomorphism testing (2015). arXiv: arXiv:1502.05912 [cs.CC]","DOI":"10.1007\/978-3-662-47672-7_13"},{"issue":"1","key":"11_CR5","doi-asserted-by":"publisher","first-page":"65","DOI":"10.2178\/jsl\/1045861507","volume":"68","author":"A Blass","year":"2003","unstructured":"Blass, A., Gurevich, Y.: Strong extension axioms and shelah\u2019s zero-one law for choiceless polynomial time. J. Symb. Logic 68(1), 65\u2013131 (2003)","journal-title":"J. Symb. Logic"},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/S0168-0072(99)00005-6","volume":"100","author":"A Blass","year":"1999","unstructured":"Blass, A., Gurevich, Y., Shelah, S.: Choiceless polynomial time. Ann. Pure Appl. Logic 100, 141\u2013187 (1999)","journal-title":"Ann. Pure Appl. Logic"},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"1093","DOI":"10.2178\/jsl\/1190150152","volume":"67","author":"A Blass","year":"2002","unstructured":"Blass, A., Gurevich, Y., Shelah, S.: On polynomial time computation over undered structures. J. Symb. Logic 67, 1093\u20131125 (2002)","journal-title":"J. Symb. Logic"},{"issue":"1","key":"11_CR8","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 J. Comput. 36(1), 16\u201327 (2006)","journal-title":"SIAM J. Comput."},{"key":"11_CR9","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. Comput. 34, 720\u2013742 (2005)","journal-title":"SIAM J. Comput."},{"key":"11_CR10","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J Cai","year":"1992","unstructured":"Cai, J., F\u00fcrer, M., Immerman, N.: An optimal lower bound on the number of variables for graph identification. Combinatorica 12, 389\u2013410 (1992)","journal-title":"Combinatorica"},{"issue":"3","key":"11_CR11","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0196-6774(84)90015-4","volume":"5","author":"DG Corneil","year":"1984","unstructured":"Corneil, D.G., Goldberg, M.K.: A non-factorial algorithm for canonical numbering of a graph. J. Algorithms 5(3), 345\u2013362 (1984)","journal-title":"J. Algorithms"},{"issue":"1","key":"11_CR12","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1145\/2728816.2728820","volume":"2","author":"A Dawar","year":"2015","unstructured":"Dawar, A.: The nature and power of fixed-point logic with counting. ACM SIGLOG News 2(1), 8\u201321 (2015)","journal-title":"ACM SIGLOG News"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Dawar, A., Grohe, M., Holm, B., Laubner, B.: Logics with rank operators. In: Proceedings of 24th IEEE Symposium on Logic in Computer Science (LICS 2009), pp. 113\u2013122 (2009)","DOI":"10.1109\/LICS.2009.24"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.apal.2007.11.011","volume":"152","author":"A Dawar","year":"2009","unstructured":"Dawar, A., Richerby, D., Rossman, B.: Choiceless polynomial time, counting and the Cai-F\u00fcrer-Immerman graphs. Ann. Pure Appl. Logic 152, 31\u201350 (2009)","journal-title":"Ann. Pure Appl. Logic"},{"key":"11_CR15","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T F\u00e9der","year":"1998","unstructured":"F\u00e9der, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM J. Comput. 28, 57\u2013104 (1998)","journal-title":"SIAM J. Comput."},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"E., Gr\u00e4del, \u0141., Kaiser, W.P., Schalth\u00f6fer, S.: Characterising choiceless polynomial time with first-order interpretations. In: LICS (2015)","DOI":"10.1109\/LICS.2015.68"},{"key":"11_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/3-540-56992-8_15","volume-title":"Computer Science Logic","author":"E Gr\u00e4del","year":"1992","unstructured":"Gr\u00e4del, E., Otto, M.: Inductive definability with counting on finite structures. In: B\u00f6rger, E., J\u00e4ger, G., B\u00fcning, H.K., Martini, S., Richter, M.M. (eds.) CSL 1992. LNCS, vol. 702, pp. 231\u2013247. Springer, Heidelberg (1992)"},{"key":"11_CR18","unstructured":"Gr\u00e4del, E., Pakusa, W.: Rank logic is dead, long live rank logic! (2015). http:\/\/arxiv.org\/abs\/1503.05423"},{"key":"11_CR19","volume-title":"Finite Model Theory and Its Applications","author":"E Gr\u00e4del","year":"2007","unstructured":"Gr\u00e4del, E., et al.: Finite Model Theory and Its Applications. Springer, New York (2007)"},{"issue":"5","key":"11_CR20","doi-asserted-by":"publisher","first-page":"27:1","DOI":"10.1145\/2371656.2371662","volume":"59","author":"M Grohe","year":"2012","unstructured":"Grohe, M.: Fixed-point definability and polynomial time on graph with excluded minors. J. ACM 59(5), 27:1\u201327:64 (2012)","journal-title":"J. ACM"},{"key":"11_CR21","doi-asserted-by":"publisher","first-page":"549","DOI":"10.2307\/2275675","volume":"61","author":"Y Gurevich","year":"1996","unstructured":"Gurevich, Y., Shelah, S.: On finite rigid structures. J. Symb. Logic 61, 549\u2013562 (1996)","journal-title":"J. Symb. Logic"},{"key":"11_CR22","unstructured":"Holm, B.: Descriptive Complexity of Linear Algebra. Ph.D. thesis, University of Cambridge (2010)"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Immerman, N.: Expresibility as a complexity measure: results and directions. In: Structure in Complexity Theory, pp. 194\u2013202 (1987)","DOI":"10.1109\/PSCT.1987.10319271"},{"key":"11_CR24","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"RE Ladner","year":"1975","unstructured":"Ladner, R.E.: On the structure of polynomial time reducibility. J. ACM 22, 155\u2013171 (1975)","journal-title":"J. ACM"},{"key":"11_CR25","unstructured":"Laubner, B.: The Structure of Graphs and New Logics for the Characterization of Polynomial Time. Ph.D. thesis, Humboldt-Universit\u00e4tt zu Berlin (2011)"},{"key":"11_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21676-7","volume-title":"Bounded Variable Logics and Counting","author":"M Otto","year":"1997","unstructured":"Otto, M.: Bounded Variable Logics and Counting. Springer, Heidelberg (1997)"},{"key":"11_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/978-3-642-15025-8_28","volume-title":"Fields of Logic and Computation","author":"B Rossman","year":"2010","unstructured":"Rossman, B.: Choiceless computation and symmetry. In: Blass, A., Dershowitz, N., Reisig, W. (eds.) Fields of logic and computation. LNCS, vol. 6300, pp. 565\u2013580. Springer, Heidelberg (2010)"}],"container-title":["Lecture Notes in Computer Science","Fields of Logic and Computation II"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-23534-9_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T23:20:21Z","timestamp":1718061621000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-23534-9_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319235332","9783319235349"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-23534-9_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"5 September 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}