{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:26:24Z","timestamp":1725456384670},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540645702"},{"type":"electronic","value":"9783540693536"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0028031","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T07:02:06Z","timestamp":1132642926000},"page":"461-477","source":"Crossref","is-referenced-by-count":5,"title":["Padding and the expressive power of existential second-order logics"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Schwentick","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,15]]},"reference":[{"issue":"1","key":"28_CR1","doi-asserted-by":"crossref","first-page":"113","DOI":"10.2307\/2274958","volume":"55","author":"M. Ajtai","year":"1990","unstructured":"M. Ajtai and R. Fagin. Reachability is harder for directed than for undirected finite graphs. Journal of Symbolic Logic, 55(1):113\u2013150, 1990.","journal-title":"Journal of Symbolic Logic"},{"issue":"1\u20132","key":"28_CR2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/S0304-3975(96)00015-1","volume":"174","author":"S. Arora","year":"1997","unstructured":"Sanjeev Arora and Ronald Fagin. On winning strategies in EhrenfeuchtFra\u00efss\u00e9 games. Theoretical Computer Science, 174(1\u20132):97\u2013121, 1997.","journal-title":"Theoretical Computer Science"},{"key":"28_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai. \u03a31 1 formulae on finite structures. Ann. of Pure and Applied Logic, 24:1\u201348, 1983.","journal-title":"Ann. of Pure and Applied Logic"},{"key":"28_CR4","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1002\/malq.19870330107","volume":"33","author":"M. Rougemont de","year":"1987","unstructured":"M. de Rougemont. Second-order and inductive definability on finite structures. Zeitschrift fur Mathematische Logik and Crundlagen der Mathematik, 33:47\u201363, 1987.","journal-title":"Zeitschrift fur Mathematische Logik and Crundlagen der Mathematik"},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer-Verlag, 1995.","DOI":"10.1007\/3-540-28788-4"},{"key":"28_CR6","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":"28_CR7","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1002\/malq.19750210112","volume":"21","author":"R. Fagin","year":"1975","unstructured":"R. Fagin. Monadic generalized spectra. Zeitschrift fur Mathematische Logik and Grundlagen der Mathematik, 21:89\u201396, 1975.","journal-title":"Zeitschrift fur Mathematische Logik and Grundlagen der Mathematik"},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"E. Grandjean and F. Olive. Monadic logical definability of NP-complete problems. In Proc. 1994 of the Annual Conference of the EACSL, pages 190\u2013204, 1994. Extended version submitted.","DOI":"10.1007\/BFb0022256"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"E. Graedel. On logical descriptions of some concepts in structural complexity classes. In E. B\u00f6rger, H. Kleine Buning, and M.M. Richter, editors, CSL '89: 3rd Workshop on Computer Science Logic, volume 440 of LNCS, pages 163\u2013175. Springer-Verlag, 1990.","DOI":"10.1007\/3-540-52753-2_38"},{"key":"28_CR10","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/0022-0000(90)90009-A","volume":"40","author":"E. Grandjean","year":"1990","unstructured":"E. Grandjean. First-order spectra with one variable. Journal of Computer and System Sciences, 40:136\u2013153, 1990.","journal-title":"Journal of Computer and System Sciences"},{"key":"28_CR11","doi-asserted-by":"crossref","unstructured":"M. Kreidler and D. Seese. Monadic NP and built-in trees. In Proceedings CSL 96, volume 1258 of LNCS, pages 260\u2013274. Springer-Verlag, 1997.Presented at CSL 96.","DOI":"10.1007\/3-540-63172-0_44"},{"issue":"2","key":"28_CR12","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0020-0190(96)00198-6","volume":"61","author":"B. Loescher","year":"1997","unstructured":"Bernd Loescher. One unary function says less than two in existential second order logic. Information Processing Letters, 61(2):69\u201375, 28 January 1997.","journal-title":"Information Processing Letters"},{"key":"28_CR13","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01786976","volume":"15","author":"J. F. Lynch","year":"1982","unstructured":"J. F. Lynch. Complexity classes and theories of finite models. Mathematical System Theory, 15:127\u2013144, 1982.","journal-title":"Mathematical System Theory"},{"key":"28_CR14","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/BF01276438","volume":"2","author":"J. F. Lynch","year":"1992","unstructured":"J. F. Lynch. The quantifier structure of sentences that characterize nondeterministic time complexity. Computational Complexity, 2:40\u201366, 1992.","journal-title":"Computational Complexity"},{"key":"28_CR15","doi-asserted-by":"crossref","unstructured":"T. Schwentick. Graph connectivity, monadic NP and built-in relations of moderate degree. In Proc. 22nd International Colloq. on Automata, Languages, and Programming, pages 405\u2013416, 1995.","DOI":"10.1007\/3-540-60084-1_92"},{"key":"28_CR16","doi-asserted-by":"crossref","unstructured":"T. Schwentick. On bijections vs. unary functions. In Proc. 13th Symposium on Theoretical Aspects of Computer Science STACS 96, pages 415\u2013426, 1996.","DOI":"10.1007\/3-540-60922-9_34"},{"key":"28_CR17","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0168-0072(95)00030-5","volume":"79","author":"T. Schwentick","year":"1996","unstructured":"T. Schwentick. On winning Ehrenfeucht games and monadic NP. Annals of Pure and Applied Logic, 79:61\u201392, 1996.","journal-title":"Annals of Pure and Applied Logic"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028031","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T02:51:08Z","timestamp":1586573468000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028031"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540645702","9783540693536"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/bfb0028031","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}