{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:17:02Z","timestamp":1781259422710,"version":"3.54.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,7,13]],"date-time":"2016-07-13T00:00:00Z","timestamp":1468368000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000735","name":"University of Cambridge","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000735","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s00224-016-9692-2","type":"journal-article","created":{"date-parts":[[2016,7,13]],"date-time":"2016-07-13T03:03:35Z","timestamp":1468379015000},"page":"521-551","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On Symmetric Circuits and Fixed-Point Logics"],"prefix":"10.1007","volume":"60","author":[{"given":"Matthew","family":"Anderson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anuj","family":"Dawar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,7,13]]},"reference":[{"key":"9692_CR1","unstructured":"Anderson, M., Dawar, A.: On symmetric circuits and fixed-point logics. In: 31st International Symposium on Theoretical Aspects of Computer Science, volume 25, pages 41\u201352 (2014)"},{"key":"9692_CR2","doi-asserted-by":"crossref","unstructured":"Anderson, M., Dawar, A., Holm, B.: Maximum matching and linear programming in fixed-point logic with counting (2013)","DOI":"10.1109\/LICS.2013.23"},{"key":"9692_CR3","doi-asserted-by":"crossref","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. Annals of Pure and Applied Logic 100, 141\u2013187 (1999)","journal-title":"Annals of Pure and Applied Logic"},{"issue":"4","key":"9692_CR4","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J-Y Cai","year":"1992","unstructured":"Cai, J-Y., F\u00fcrer, M., Immerman, N.: An optimal lower bound on the number of variables for graph identification. Combinatorica 12(4), 389\u2013410 (1992)","journal-title":"Combinatorica"},{"issue":"3","key":"9692_CR5","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1137\/0220036","volume":"20","author":"P Clote","year":"1991","unstructured":"Clote, P., Kranakis, E.: Boolean functions, invariance groups, and parallel complexity. SIAM J. Comput. 20(3), 553\u2013590 (1991)","journal-title":"SIAM J. Comput."},{"key":"9692_CR6","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1006\/inco.1998.2703","volume":"143","author":"A Dawar","year":"1998","unstructured":"Dawar, A.: A restricted second order logic for finite structures. Inf. Comput. 143, 154\u2013174 (1998)","journal-title":"Inf. Comput."},{"key":"9692_CR7","doi-asserted-by":"crossref","first-page":"65","DOI":"10.2178\/bsl\/1182353853","volume":"8","author":"A Dawar","year":"2002","unstructured":"Dawar, A., Gurevich, Y.: Fixed point logics. Bull. Symb. Log. 8, 65\u201388 (2002)","journal-title":"Bull. Symb. Log."},{"key":"9692_CR8","doi-asserted-by":"crossref","unstructured":"Dawar, A., Lindell, S., Weinstein, S.: First order logic, fixed point logic and linear order. In: Kleine-B\u00fcning, H. (ed.) Computer Science Logic \u201995, volume 1092 of LNCS, pages 161\u2013177. Springer-Verlag (1996)","DOI":"10.1007\/3-540-61377-3_37"},{"issue":"1","key":"9692_CR9","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.apal.2007.11.011","volume":"152","author":"A Dawar","year":"2008","unstructured":"Dawar, A., Richerby, D., Rossman, B.: Choiceless polynomial time, counting and the Cai\u2013F\u00fcrer\u2013Immerman graphs. Annals of Pure and Applied Logic 152(1), 31\u201350 (2008)","journal-title":"Annals of Pure and Applied Logic"},{"issue":"2","key":"9692_CR10","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/S0019-9958(86)80006-7","volume":"70","author":"L Denenberg","year":"1986","unstructured":"Denenberg, L., Gurevich, Y., Shelah, S.: Definability by constant-depth polynomial-size circuits. Inf. Control. 70(2), 216\u2013240 (1986)","journal-title":"Inf. Control."},{"key":"9692_CR11","unstructured":"Ebbinghaus, H.D., Flum, J.: Finite Model Theory. Springer (1999)"},{"key":"9692_CR12","doi-asserted-by":"crossref","unstructured":"Furst, M., Hopcroft, J., Luks, E.: Polynomial-time algorithms for permutation groups. In: Proceedings of the Twenty-First Annual ACM Symposium on Foundations of Computer Science, pages 36\u201341. IEEE (1980)","DOI":"10.1109\/SFCS.1980.34"},{"issue":"5","key":"9692_CR13","doi-asserted-by":"crossref","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 graphs with excluded minors. J. ACM 59(5), 27:1\u201327:64 (2012)","journal-title":"J. ACM"},{"issue":"1-3","key":"9692_CR14","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N Immerman","year":"1986","unstructured":"Immerman, N.: Relational queries computable in polynomial time. Inf. Control. 68(1-3), 86\u2013104 (1986)","journal-title":"Inf. Control."},{"key":"9692_CR15","doi-asserted-by":"crossref","unstructured":"Immerman, N.: Descriptive Complexity Theory. Springer (1999)","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"9692_CR16","doi-asserted-by":"crossref","unstructured":"Otto, M.: Bounded Variable Logics and Counting: A Study in Finite Models, volume 9 of Lecture Notes in Logic. Springer-Verlag (1997)","DOI":"10.1007\/978-3-662-21676-7"},{"key":"9692_CR17","doi-asserted-by":"crossref","unstructured":"Otto, M.: The logic of explicitly presentation-invariant circuits. In: Dalen, D., Bezem, M. (eds.) Computer Science Logic, volume 1258 of Lecture Notes in Computer Science, pages 369\u2013384. Springer Berlin Heidelberg (1997)","DOI":"10.1007\/3-540-63172-0_50"},{"key":"9692_CR18","doi-asserted-by":"crossref","unstructured":"Ryser, H.J.: Combinatorial Mathematics. Mathematical Association of America (1963)","DOI":"10.5948\/UPO9781614440147"},{"key":"9692_CR19","doi-asserted-by":"crossref","unstructured":"Vardi, M.: The complexity of relational query languages (1982)","DOI":"10.1145\/800070.802186"},{"key":"9692_CR20","doi-asserted-by":"crossref","unstructured":"Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer-Verlag Berlin Heidelberg (1999)","DOI":"10.1007\/978-3-662-03927-4"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9692-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9692-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9692-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9692-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,23]],"date-time":"2020-09-23T21:37:44Z","timestamp":1600897064000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9692-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,13]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["9692"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9692-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7,13]]}}}