{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:47:35Z","timestamp":1725558455713},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540408017"},{"type":"electronic","value":"9783540452201"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45220-1_16","type":"book-chapter","created":{"date-parts":[[2010,6,25]],"date-time":"2010-06-25T23:33:58Z","timestamp":1277508838000},"page":"169-182","source":"Crossref","is-referenced-by-count":5,"title":["A Fixed-Point Logic with Symmetric Choice"],"prefix":"10.1007","author":[{"given":"Anuj","family":"Dawar","sequence":"first","affiliation":[]},{"given":"David","family":"Richerby","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/BFb0039616","volume-title":"STACS 87","author":"V. Arvind","year":"1987","unstructured":"Arvind, V., Biswas, S.: Expressibility of first order logic with a nondeterministic inductive operator. In: Brandenburg, F.J., Wirsing, M., Vidal-Naquet, G. (eds.) STACS 1987. LNCS, vol.\u00a0247, pp. 323\u2013335. Springer, Heidelberg (1987)"},{"issue":"3","key":"16_CR2","doi-asserted-by":"publisher","first-page":"1264","DOI":"10.2307\/2586700","volume":"65","author":"A. Blass","year":"2000","unstructured":"Blass, A., Gurevich, Y.: The logic of choice. Journal of Symbolic Logic\u00a065(3), 1264\u20131310 (2000)","journal-title":"Journal of Symbolic Logic"},{"issue":"2","key":"16_CR3","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R.B. Boppana","year":"1987","unstructured":"Boppana, R.B., H\u00e5stad, J., Zachos, S.: Does co-NP have short interactive proofs? Information Processing Letters\u00a025(2), 127\u2013132 (1987)","journal-title":"Information Processing Letters"},{"issue":"4","key":"16_CR4","doi-asserted-by":"publisher","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\u00a012(4), 389\u2013410 (1992)","journal-title":"Combinatorica"},{"issue":"2","key":"16_CR5","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1093\/logcom\/5.2.213","volume":"5","author":"A. Dawar","year":"1995","unstructured":"Dawar, A.: Generalized quantifiers and logical reducibilities. Journal of Logic and Computation\u00a05(2), 213\u2013226 (1995)","journal-title":"Journal of Logic and Computation"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Dawar, A., Richerby, D.M.: Fixed-point logics with nondeterministic choice. Journal of Logic and Computation (to appear)","DOI":"10.1093\/logcom\/13.4.503"},{"key":"16_CR7","first-page":"25","volume-title":"Model-Theoretic Logics, Perspectives in Mathematical Logic","author":"H.-D. Ebbinghaus","year":"1985","unstructured":"Ebbinghaus, H.-D.: Extended logics: The general framework. In: Barwise, J., Feferman, S. (eds.) Model-Theoretic Logics, Perspectives in Mathematical Logic, pp. 25\u201376. Springer, Heidelberg (1985)"},{"key":"16_CR8","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":"16_CR9","unstructured":"Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Karp, R. (ed.) Complexity of Computation. SIAM-AMS Proceedings, vol.\u00a07, pp. 43\u201373. SIAM-AMS (1974)"},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1006\/inco.1998.2712","volume":"144","author":"F. Gire","year":"1998","unstructured":"Gire, F., Hoang, H.K.: An extension of fixpoint logic with a symmetrybased choice construct. Information and Computation\u00a0144, 40\u201365 (1998)","journal-title":"Information and Computation"},{"key":"16_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/3-540-49257-7_6","volume-title":"Database Theory - ICDT\u201999","author":"M. Grohe","year":"1998","unstructured":"Grohe, M., Mari\u00f1o, J.: Definability and descriptive complexity on databases of bounded tree-width. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol.\u00a01540, pp. 70\u201382. Springer, Heidelberg (1998)"},{"key":"16_CR12","first-page":"6","volume-title":"Proceedings of 13th IEEE Annual Symposium on Logic in Computer Science","author":"M. Grohe","year":"1998","unstructured":"Grohe, M.: Fixed-point logics on planar graphs. In: Proceedings of 13th IEEE Annual Symposium on Logic in Computer Science, pp. 6\u201315. IEEE Computer Society, Los Alamitos (1998)"},{"key":"16_CR13","first-page":"63","volume-title":"Proceedings of 32nd ACM Symposium on Theory of Computing","author":"M. Grohe","year":"2000","unstructured":"Grohe, M.: Isomorphism testing for embeddable graphs through definability. In: Proceedings of 32nd ACM Symposium on Theory of Computing, pp. 63\u201372. ACM, New York (2000)"},{"key":"16_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/3-540-58201-0_61","volume-title":"Automata, Languages, and Programming","author":"M. Gyssens","year":"1994","unstructured":"Gyssens, M., Van den Bussche, J., Van Gucht, D.: Expressiveness of efficient semi-deterministic choice constructs. In: Shamir, E., Abiteboul, S. (eds.) ICALP 1994. LNCS, vol.\u00a0820, pp. 106\u2013117. Springer, Heidelberg (1994)"},{"key":"16_CR15","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/978-1-4612-4478-3_5","volume-title":"Complexity Theory Retrospective","author":"N. Immerman","year":"1990","unstructured":"Immerman, N., Lander, E.S.: Describing graphs: A first-order approach to graph canonization. In: Selman, A. (ed.) Complexity Theory Retrospective, pp. 59\u201381. Springer, Heidelberg (1990)"},{"issue":"1\u20133","key":"16_CR16","doi-asserted-by":"publisher","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. Information and Control\u00a068(1\u20133), 86\u2013104 (1986)","journal-title":"Information and Control"},{"key":"16_CR17","series-title":"Lecture Notes in Logic","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-21676-7","volume-title":"Bounded Variable Logics and Counting \u2014 A Study in Finite Models","author":"M. Otto","year":"1997","unstructured":"Otto, M.: Bounded Variable Logics and Counting \u2014 A Study in Finite Models. Lecture Notes in Logic, vol.\u00a09. Springer, Heidelberg (1997)"},{"issue":"3","key":"16_CR18","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1016\/0022-0000(88)90010-4","volume":"37","author":"U. Sch\u00f6ning","year":"1988","unstructured":"Sch\u00f6ning, U.: Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences\u00a037(3), 312\u2013323 (1988)","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR19","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1109\/SFCS.2000.892080","volume-title":"Proceedings of 41st Annual Symposium on Foundations of Computer Science","author":"J. Tor\u00e1n","year":"2000","unstructured":"Tor\u00e1n, J.: On the hardness of graph isomorphism. In: Proceedings of 41st Annual Symposium on Foundations of Computer Science, pp. 180\u2013186. IEEE Computer Society, Los Alamitos (2000)"},{"key":"16_CR20","first-page":"137","volume-title":"Proceedings of 14th ACM Symposium on Theory of Computing","author":"M.Y. Vardi","year":"1982","unstructured":"Vardi, M.Y.: Complexity of relational query languages. In: Proceedings of 14th ACM Symposium on Theory of Computing, pp. 137\u2013146. ACM, New York (1982)"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45220-1_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T03:08:25Z","timestamp":1552619305000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45220-1_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540408017","9783540452201"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45220-1_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}