{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:40:24Z","timestamp":1742600424077,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_34","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:04:16Z","timestamp":1330290256000},"page":"415-426","source":"Crossref","is-referenced-by-count":3,"title":["On bijections vs. unary functions"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Schwentick","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"issue":"1","key":"34_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"},{"key":"34_CR2","unstructured":"S. Arora and R. Fagin. On winning strategies in Ehrenfeucht-Fra\u00efss\u00e9 games. Unpublished manuscript, 1994."},{"key":"34_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. \u03a3 1 1 formulae on finite structures. Ann. of Pure and Applied Logic, 24:1\u201348, 1983.","journal-title":"Ann. of Pure and Applied Logic"},{"key":"34_CR4","doi-asserted-by":"crossref","unstructured":"S. Cosmadakis. Logical reducibility and monadic NP. In Proc. 34th IEEE Symp. on Foundations of Computer Science, pages 52\u201361, 1993.","DOI":"10.1109\/SFCS.1993.366882"},{"key":"34_CR5","unstructured":"A. Durand, C. Lautemann, and T. Schwentick. Fragments of binary NP. In Annual Conference of the EACSL, 1995."},{"key":"34_CR6","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 f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 33:47\u201363, 1987.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"34_CR7","unstructured":"H.-D. Ebbinghaus, J. Flum, and W. Thomas. Einf\u00fchrung in die mathematische Logik. BI, Mannheim, 3rd edition, 1992."},{"key":"34_CR8","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","volume":"49","author":"A. Ehrenfeucht","year":"1961","unstructured":"A. Ehrenfeucht. An application of games to the completeness problem for formalized theories. Fund. Math., 49:129\u2013141, 1961.","journal-title":"Fund. Math."},{"key":"34_CR9","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":"34_CR10","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 f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 21:89\u201396, 1975.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"34_CR11","first-page":"35","volume":"1","author":"R. Fra\u00efss\u00e9","year":"1954","unstructured":"R. Fra\u00efss\u00e9. Sur quelques classifications des syst\u00e8mes de relations. Publ. Sci. Univ. Alger. S\u00e9r. A, 1:35\u2013182, 1954.","journal-title":"Publ. Sci. Univ. Alger. S\u00e9r. A"},{"key":"34_CR12","doi-asserted-by":"crossref","unstructured":"R. Fagin, L. Stockmeyer, and M. Vardi. On monadic NP vs. monadic co-NP. In The Proceedings of the 8th Annual IEEE Conference on Structure in Complexity Theory, pages 19\u201330, 1993.","DOI":"10.1109\/SCT.1993.336544"},{"key":"34_CR13","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1137\/0213025","volume":"13","author":"E. Grandjean","year":"1984","unstructured":"E. Grandjean. The spectra of first-order sentences and computational complexity. SIAM Journal on Computing, 13:356\u2013373, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"34_CR14","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF01699468","volume":"13","author":"E. Grandjean","year":"1985","unstructured":"E. Grandjean. Universal quantifiers and. time complexity of random access machines. Mathematical System Theory, 13:171\u2013187, 1985.","journal-title":"Mathematical System Theory"},{"key":"34_CR15","doi-asserted-by":"crossref","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":"34_CR16","unstructured":"B. Loescher. Begr\u00fcndung, Verallgemeinerung und Anwendung der Ehrenfeucht-Spiele in der Relationentheorie von Roland Fra\u00efss\u00e9. Informatik-bericht 2\/91, Institut f\u00fcr Informatik, Universit\u00e4t Mainz, 1991."},{"key":"34_CR17","unstructured":"B. Loescher and A. Sharell. Functions vs. relations on finite structures \u2014 a finer hierarchy in existential second order logic. presented at ASL-Logic Colloquium, FMT-23, Haifa, 1995."},{"key":"34_CR18","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":"34_CR19","unstructured":"J. Nurmonen. On winning strategies with unary quantifiers. Preprint 77, Department of mathematics, University of Helsinki, 1995."},{"key":"34_CR20","doi-asserted-by":"crossref","unstructured":"T. Schwentick. Graph connectivity and monadic NP. In Proc. 35th IEEE Symp. on Foundations of Computer Science, pages 614\u2013622, 1994.","DOI":"10.1109\/SFCS.1994.365730"},{"key":"34_CR21","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":"34_CR22","unstructured":"M. Sekanina. On an ordering of the set of vertices of a connected graph. Spisy P\u0159\u00edrod. Fak. Univ. Brno, pages 137\u2013141, 1960."},{"key":"34_CR23","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1017\/S1446788700020681","volume":"20","author":"R. Tenney","year":"1975","unstructured":"R. Tenney. Second-order Ehrenfeucht games and the decidability of the second-order theory of an equivalence relation. Journal of the Australian Mathematical Society, 20:323\u2013331, 1975.","journal-title":"Journal of the Australian Mathematical Society"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_34.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:10:43Z","timestamp":1742598643000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}