{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:01:25Z","timestamp":1725663685125},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540569923"},{"type":"electronic","value":"9783540478904"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56992-8_15","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:00:15Z","timestamp":1330257615000},"page":"231-247","source":"Crossref","is-referenced-by-count":22,"title":["Inductive definability with counting on finite structures"],"prefix":"10.1007","author":[{"given":"Erich","family":"Gr\u00e4del","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Otto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"S. Abiteboul, M. Vardi and V. Vianu, Fixpoint Logics, Relational Machines and Computational Complexity, Proceedings of 7th IEEE Symposium on Structure in Complexity Theory (1992).","DOI":"10.1109\/SCT.1992.215391"},{"key":"15_CR2","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/0022-0000(91)90032-Z","volume":"43","author":"S. Abiteboul","year":"1991","unstructured":"S. Abiteboul and V. Vianu, Datalog Extensions for Database Queries and Updates, J. Comp. Syst. Sciences 43 (1991), 62\u2013124.","journal-title":"J. Comp. Syst. Sciences"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"S. Abiteboul and V. Vianu, Generic Computation and Its Complexity, Proceedings of 23rd ACM Symposium on Theory of Computing (1991).","DOI":"10.1145\/103418.103444"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"A. Blass and Y. Gurevich, Existential fixed-point logic, in: \u201cComputation Theory and Logic\u201d (E. B\u00f6rger, Ed.), Lecture Notes in Computer Science Nr. 270, Springer 1987, 20\u201336.","DOI":"10.1007\/3-540-18170-9_151"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"J. Cai, M. F\u00fcrer and N. Immerman, An Optimal Lower Bound on the Number of Variables for Graph Identification, Proceedings of 30th IEEE Symposium on Foundations of Computer Science (1989), 612\u2013617.","DOI":"10.1109\/SFCS.1989.63543"},{"key":"15_CR6","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","volume":"25","author":"A. Chandra","year":"1982","unstructured":"A. Chandra and D. Harel, Structure and Complexity of Relational Queries, J. Comp. Syst. Sciences 25 (1982), 99\u2013128.","journal-title":"J. Comp. Syst. Sciences"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"E. Dahlhaus, Skolem Normal Forms Concerning the Least Fixed Point, in: \u201cComputation Theory and Logic\u201d (E. B\u00f6rger, Ed.), Lecture Notes in Computer Science Nr. 270, Springer 1987, 101\u2013106.","DOI":"10.1007\/3-540-18170-9_158"},{"key":"15_CR8","unstructured":"A. Dawar, S. Lindell and S. Weinstein, Infinitary Logic and Inductive Definability over Finite Structures, Technical Report, University of Pennsylvania, (1991)."},{"key":"15_CR9","unstructured":"P. Dublish and S. Maheshwari, Query Languages which Express all PTIME Queries for Trees, Hildesheimer Informatik-Berichte 2 (1989)."},{"key":"15_CR10","unstructured":"S. Grumbach and C. Tollu, The Generic Complexity of Query Languages with Counters, Proceedings of Third Workshop on Foundations of Models and Languages for Data and Objects, Aigen (Austria) 1991."},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Y. Gurevich, Algebras of feasible functions, Proceedings of 24th IEEE Symposium on Foundations of Computer Science 1983, 210\u2013214.","DOI":"10.1109\/SFCS.1983.5"},{"key":"15_CR12","unstructured":"Y. Gurevich, Logic and the Challenge of Computer Science, in: E. B\u00f6rger (Ed), Trends in Theoretical Computer Science, Computer Science Press (1988), 1\u201357."},{"key":"15_CR13","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0168-0072(86)90055-2","volume":"32","author":"Y. Gurevich","year":"1986","unstructured":"Y. Gurevich and S. Shelah, Fixed Point Extensions of First Order Logic, Annals of Pure and Applied Logic 32 (1986), 265\u2013280.","journal-title":"Annals of Pure and Applied Logic"},{"key":"15_CR14","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"N. Immerman, Relational Queries Computable in Polynomial Time, Information and Control 68 (1986), 86\u2013104.","journal-title":"Information and Control"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"N. Immerman, Expressibility as a Complexity Measure: Results and Directions, Proc. of 2nd Conf. on Structure in Complexity Theory (1987), 194\u2013202.","DOI":"10.1109\/PSCT.1987.10319271"},{"key":"15_CR16","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/978-1-4612-4478-3_5","volume-title":"Complexity Theory Retrospective. (In Honor of Juris Hartmanis)","author":"N. Immerman","year":"1990","unstructured":"N. Immerman and E. Lander, Describing Graphs: A First Order Approach to Graph Canonization, in: A. Selman (Ed), Complexity Theory Retrospective. (In Honor of Juris Hartmanis), Springer, New York 1990, 59\u201381."},{"key":"15_CR17","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0890-5401(91)90059-B","volume":"90","author":"P. Kolaitis","year":"1991","unstructured":"Ph. Kolaitis, The Expressive Power of Stratified Logic Programs, Information and Computation 90 (1991), 50\u201366.","journal-title":"Information and Computation"},{"key":"15_CR18","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0890-5401(90)90006-4","volume":"89","author":"D. Leivant","year":"1990","unstructured":"D. Leivant, Inductive Definitions over Finite Structures, Information and Computation 89 (1990), 95\u2013108.","journal-title":"Information and Computation"},{"key":"15_CR19","unstructured":"M. Otto, The Expressive Power of Fixed-Point Logic with Counting, submitted for publication."},{"key":"15_CR20","first-page":"373","volume":"27","author":"N. Rescher","year":"1962","unstructured":"N. Rescher, Plurality Quantification, JSL 27 (1962), 373\u2013374.","journal-title":"JSL"},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"M. Vardi, Complexity of Relational Query Languages, Proc. of 14th ACM Symposium on Theory of Computing (1982), 137\u2013146.","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56992-8_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T15:05:08Z","timestamp":1713625508000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56992-8_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540569923","9783540478904"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-56992-8_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}