{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:13:37Z","timestamp":1725664417961},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540601784"},{"type":"electronic","value":"9783540447207"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60178-3_94","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:49:43Z","timestamp":1330278583000},"page":"393-413","source":"Crossref","is-referenced-by-count":7,"title":["A restricted second order logic for finite structures"],"prefix":"10.1007","author":[{"given":"Anuj","family":"Dawar","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"19_CR1","unstructured":"S. Abiteboul, Moshe Y. Vardi, and V. Vianu. Fixpoint logics, relational machines, and computational complexity. In Proc. 7th IEEE Symp. on Structure in Complexity Theory, 1992."},{"key":"19_CR2","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences, 43:62\u2013124, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"S. Abiteboul and V. Vianu. Generic computation and its complexity. In Proceedings of the 23rd ACM Symposium on the Theory of Computing, 1991.","DOI":"10.1145\/103418.103444"},{"key":"19_CR4","doi-asserted-by":"crossref","first-page":"292","DOI":"10.2307\/2272133","volume":"42","author":"J. Barwise","year":"1977","unstructured":"J. Barwise. On Moschovakis closure ordinals. Journal of Symbolic Logic, 42:292\u2013296, 1977.","journal-title":"Journal of Symbolic Logic"},{"issue":"4","key":"19_CR5","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J. Cai","year":"1992","unstructured":"J-y. Cai, M. F\u00fcrer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389\u2013410, 1992.","journal-title":"Combinatorica"},{"key":"19_CR6","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences, 25:99\u2013128, 1982.","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"E. Dahlhaus. Reduction to NP-complete problems by interpretation. In LNCS 171, pages 357\u2013365. Springer-Verlag, 1984.","DOI":"10.1007\/3-540-13331-3_51"},{"key":"19_CR8","unstructured":"A. Dawar. Feasible Computation through Model Theory. PhD thesis, University of Pennsylvania, 1993."},{"key":"19_CR9","unstructured":"A. Dawar and E.Gr\u00e4del. Generalized quantifiers and 0-1 laws. Manuscript, 1994."},{"key":"19_CR10","unstructured":"A. Dawar, S. Lindell, and S. Weinstein. Infinitary logic and inductive definability over finite structures. Technical Report MS-CIS-91-97, University of Pennsylvania, 1991. Revised version to appear in Information and Computation."},{"key":"19_CR11","unstructured":"R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In R. M. Karp, editor, Complexity of Computation, SIAM-AMS Proceedings, Vol 7, pages 43\u201373, 1974."},{"key":"19_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979."},{"key":"19_CR13","doi-asserted-by":"publisher","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:265\u2013280, 1986.","journal-title":"Annals of Pure and Applied Logic"},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/0022-0000(82)90011-3","volume":"25","author":"N. Immerman","year":"1982","unstructured":"N. Immerman. Upper and lower bounds for first-order expressibility. Journal of Computer and System Sciences, 25:76\u201398, 1982.","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR15","doi-asserted-by":"publisher","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:86\u2013104, 1986.","journal-title":"Information and Control"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"N. Immerman. Descriptive and computational complexity. In J. Hartmanis, editor, Computational Complexity Theory, Proc. of AMS Symposia in Appl. Math., volume 38, pages 75\u201391, 1989.","DOI":"10.1090\/psapm\/038\/1020810"},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"Ph. G. Kolaitis and M. Y. Vardi. Fixpoint logic vs. infinitary logic in finite-model theory. In Proc. 7th IEEE Symp. on Logic in Computer Science, pages 46\u201357, 1992.","DOI":"10.1109\/LICS.1992.185518"},{"issue":"2","key":"19_CR18","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/0890-5401(92)90021-7","volume":"98","author":"P. G. Kolaitis","year":"1992","unstructured":"Ph. G. Kolaitis and M. Y. Vardi. Infinitary logics and 0-1 laws. Information and Computation, 98(2):258\u2013294, 1992.","journal-title":"Information and Computation"},{"key":"19_CR19","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:95\u2013108, 1990.","journal-title":"Information and Computation"},{"key":"19_CR20","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1002\/malq.19770233608","volume":"23","author":"L. Lov\u00e1sz","year":"1977","unstructured":"L. Lov\u00e1sz and P. G\u00e1cs. Some remarks on generalized spectra. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 23:27\u2013144, 1977.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"19_CR21","unstructured":"Y. N. Moschovakis. Elementary Induction on Abstract Structures. North Holland, 1974."},{"key":"19_CR22","unstructured":"A.Rubin. Free Algebras in Von Neumann-Bernays-Godel Set Theory and Positive Elementary Inductions in Reasonable Structures. PhD thesis, California Institute of Technology, 1975."},{"key":"19_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1976","unstructured":"L. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3:1\u201322, 1976.","journal-title":"Theoretical Computer Science"},{"key":"19_CR24","doi-asserted-by":"crossref","unstructured":"M. Y. Vardi. The complexity of relational query languages. In Proceedings of the 14th ACM Symposium on the Theory of Computing, pages 137\u2013146, 1982.","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Logic and Computational Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60178-3_94.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:55:49Z","timestamp":1605646549000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60178-3_94"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540601784","9783540447207"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-60178-3_94","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}