{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:37:49Z","timestamp":1787506669272,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":53,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540659228","type":"print"},{"value":"9783540488552","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/10703163_2","type":"book-chapter","created":{"date-parts":[[2006,10,9]],"date-time":"2006-10-09T14:15:50Z","timestamp":1160403350000},"page":"9-28","source":"Crossref","is-referenced-by-count":3,"title":["Descriptive Complexity, Lower Bounds and Linear Time"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Schwentick","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"Ajtai, M.: \u03a31 1 formulae on finite structures. Ann. of Pure and Applied Logic\u00a024, 1\u201348 (1983)","journal-title":"Ann. of Pure and Applied Logic"},{"issue":"1","key":"2_CR2","doi-asserted-by":"publisher","first-page":"113","DOI":"10.2307\/2274958","volume":"55","author":"M. Ajtai","year":"1990","unstructured":"Ajtai, M., Fagin, R.: Reachability is harder for directed than for undirected nite graphs. Journal of Symbolic Logic\u00a055(1), 113\u2013150 (1990)","journal-title":"Journal of Symbolic Logic"},{"key":"2_CR3","unstructured":"Ajtai, M., Fagin, R., Stockmeyer, L.: The closure of monadic NP. IBM Research Report RJ 10092 (1997)"},{"issue":"1-2","key":"2_CR4","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/S0304-3975(96)00015-1","volume":"174","author":"S. Arora","year":"1997","unstructured":"Arora, S., Fagin, R.: On winning strategies in Ehrenfeucht-Fra\u00efss\u00e9 games. Theoretical Computer Science\u00a0174(1-2), 97\u2013121 (1997)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"2_CR5","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"Baker, T., Gill, J., Solovay, R.: Relativizations of the P =? NP question. SIAM Journal on Computing\u00a04(4), 431\u2013442 (1975)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"2_CR6","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01705890","volume":"4","author":"R.V. Book","year":"1970","unstructured":"Book, R.V., Greibach, S.A.: Quasi-realtime languages. Mathematical System Theory\u00a04(2), 97\u2013111 (1970)","journal-title":"Mathematical System Theory"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"R. B\u00fcchi","year":"1960","unstructured":"B\u00fcchi, R.: Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math.\u00a06, 66\u201392 (1960)","journal-title":"Z. Math. Logik Grundlagen Math."},{"issue":"4","key":"2_CR8","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0022-0000(73)80028-5","volume":"7","author":"S.A. Cook","year":"1973","unstructured":"Cook, S.A.: A hierarchy for nondeterministic time complexity. Journal of Computer and System Sciences\u00a07(4), 343\u2013353 (1973)","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Cosmadakis, S.: Logical reducibility and monadic NP. In: Proc. 34th IEEE Symp. on Foundations of Computer Science, pp. 52\u201361 (1993)","DOI":"10.1109\/SFCS.1993.366882"},{"key":"2_CR10","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1002\/malq.19870330107","volume":"33","author":"M. Rougemont de","year":"1987","unstructured":"de Rougemont, M.: Second-order and inductive definability on finite structures. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik\u00a033, 47\u201363 (1987)","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"2_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BFb0028015","volume-title":"11th Annual Conference of the EACSL, CSL 1997","author":"A. Durand","year":"1998","unstructured":"Durand, A., Fagin, R., Loescher, B.: Spectra with only unary function symbols. In: Nielsen, M. (ed.) CSL 1997. LNCS, vol.\u00a01414, pp. 189\u2013202. Springer, Heidelberg (1998)"},{"issue":"2","key":"2_CR12","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1093\/logcom\/8.2.189","volume":"8","author":"A. Durand","year":"1998","unstructured":"Durand, A., Lautemann, C., Schwentick, T.: Subclasses of binary NP. Journal of Logic and Computation\u00a08(2), 189\u2013207 (1998)","journal-title":"Journal of Logic and Computation"},{"issue":"1-2","key":"2_CR13","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0304-3975(95)00112-3","volume":"160","author":"A. Durand","year":"1996","unstructured":"Durand, A., Ranaivoson, S.: First-order spectra with one binary predicate. Theoretical Computer Science\u00a0160(1-2), 305\u2013320 (1996)","journal-title":"Theoretical Computer Science"},{"key":"2_CR14","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1995","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory. Springer, Heidelberg (1995)"},{"key":"2_CR15","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","volume":"49","author":"A. Ehrenfeucht","year":"1961","unstructured":"Ehrenfeucht, A.: An application of games to the completeness problem for formalized theories. Fund. Math.\u00a049, 129\u2013141 (1961)","journal-title":"Fund. Math."},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Eiter, T., Gottlob, G., Gurevich, Y.: Existential second-order logic over strings. In: LICS 1998 (1998)","DOI":"10.1109\/LICS.1998.705640"},{"key":"2_CR17","unstructured":"Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Karp, R.M. (ed.) Complexity of Computation, SIAM-AMS Proceedings, vol.\u00a07, pp. 43\u201373 (1974)"},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1002\/malq.19750210112","volume":"21","author":"R. Fagin","year":"1975","unstructured":"Fagin, R.: Monadic generalized spectra. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik\u00a021, 89\u201396 (1975)","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"2_CR19","volume-title":"Proceedings of the DIMACS Workshop on Finite Models and Descriptive Complexity","author":"R. Fagin","year":"1997","unstructured":"Fagin, R.: Easier ways to win logical games. In: Proceedings of the DIMACS Workshop on Finite Models and Descriptive Complexity. American Mathematical Society, Providence (1997)"},{"key":"2_CR20","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1006\/inco.1995.1100","volume":"120","author":"R. Fagin","year":"1995","unstructured":"Fagin, R., Stockmeyer, L., Vardi, M.: On monadic NP vs. monadic co-NP. Information and Computation\u00a0120, 78\u201392 (1995); Preliminary version appeared in 1993 IEEE Conference on Structure in Complexity Theory, pp. 19-30 (1993)","journal-title":"Information and Computation"},{"key":"2_CR21","first-page":"35","volume":"1","author":"R. Fra\u00efss\u00e9","year":"1954","unstructured":"Fra\u00efss\u00e9, R.: Sur quelques classifications des syst\u00e8mes de relations. Publ. Sci. Univ. Alger. S\u00e9r. A\u00a01, 35\u2013182 (1954)","journal-title":"Publ. Sci. Univ. Alger. S\u00e9r. A"},{"key":"2_CR22","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1142\/S0129054190000217","volume":"1","author":"E. Gr\u00e4del","year":"1990","unstructured":"Gr\u00e4del, E.: On the notion of linear time computability. Int. J. Found. Comput. Sci.\u00a01, 295\u2013307 (1990)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"2_CR23","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1137\/0217050","volume":"17","author":"E. Grandjean","year":"1988","unstructured":"Grandjean, E.: A natural NP-complete problem with a nontrivial lower bound. SIAM Journal of Computing\u00a017, 786\u2013809 (1988)","journal-title":"SIAM Journal of Computing"},{"key":"2_CR24","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/BF01205055","volume":"4","author":"E. Grandjean","year":"1994","unstructured":"Grandjean, E.: Invariance properties of RAMs and linear time. Computational Complexity\u00a04, 62\u2013106 (1994)","journal-title":"Computational Complexity"},{"key":"2_CR25","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1137\/S0097539791223206","volume":"23","author":"E. Grandjean","year":"1994","unstructured":"Grandjean, E.: Linear time algorithms and NP-complete problems. SIAM Journal of Computing\u00a023, 573\u2013597 (1994)","journal-title":"SIAM Journal of Computing"},{"key":"2_CR26","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF02127798","volume":"16","author":"E. Grandjean","year":"1996","unstructured":"Grandjean, E.: Sorting, linear time and the satisfiability problem. Annals of Mathematics and Artificial Intelligence\u00a016, 183\u2013236 (1996)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"2_CR27","doi-asserted-by":"crossref","unstructured":"Grandjean, E., Olive, F.: Monadic logical definability of NP-complete problems. In: Proc. 1994 of the Annual Conference of the EACSL, pp. 190\u2013204 (1994) (Extended version submitted)","DOI":"10.1007\/BFb0022256"},{"key":"2_CR28","unstructured":"Grandjean, E., Schwentick, T.: Machine-independent characterizations and complete problems for deterministic linear time (1998) (in preparation)"},{"key":"2_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/3-540-51237-3_10","volume-title":"Logic at Botik 1989","author":"Y. Gurevich","year":"1989","unstructured":"Gurevich, Y., Shelah, S.: Nearly linear time. In: Meyer, A.R., Taitslin, M.A. (eds.) Logic at Botik 1989. LNCS, vol.\u00a0363, pp. 108\u2013118. Springer, Heidelberg (1989)"},{"key":"2_CR30","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"Hartmanis, J., Stearns, R.E.: On the computational complexity of algorithms. Transactions of the AMS\u00a0117, 285\u2013306 (1965)","journal-title":"Transactions of the AMS"},{"issue":"2","key":"2_CR31","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1145\/322003.322015","volume":"24","author":"J. Hopcroft","year":"1977","unstructured":"Hopcroft, J., Paul, W., Valiant, L.: On time versus space. Journal of the ACM\u00a024(2), 332\u2013337 (1977)","journal-title":"Journal of the ACM"},{"key":"2_CR32","volume-title":"Graduate Texts in Computer Science","author":"N. Immerman","year":"1998","unstructured":"Immerman, N.: Descriptive Complexity. In: Graduate Texts in Computer Science. Springer, New York (1998)"},{"key":"2_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/3-540-63172-0_44","volume-title":"Proceedings CSL 1996","author":"M. Kreidler","year":"1997","unstructured":"Kreidler, M., Seese, D.: Monadic NP and built-in trees. In: van Dalen, D., Bezem, M. (eds.) CSL 1996. LNCS, vol.\u00a01258, pp. 260\u2013274. Springer, Heidelberg (1997)"},{"key":"2_CR34","doi-asserted-by":"crossref","unstructured":"Kreidler, M., Seese, D.: Monadic NP and graph minors. In: CSL 1998 (1998)","DOI":"10.1007\/10703163_9"},{"key":"2_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/3-540-49116-3_13","volume-title":"STACS 99","author":"C. Lautemann","year":"1999","unstructured":"Lautemann, C., Schweikardt, N., Schwentick, T.: A logical characterization of nondeterministic linear time on Turing machines. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, p. 143. Springer, Heidelberg (1999)"},{"key":"2_CR36","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01786976","volume":"15","author":"J.F. Lynch","year":"1982","unstructured":"Lynch, J.F.: Complexity classes and theories of finite models. Mathematical System Theory\u00a015, 127\u2013144 (1982)","journal-title":"Mathematical System Theory"},{"key":"2_CR37","doi-asserted-by":"publisher","first-page":"659","DOI":"10.2307\/2273595","volume":"47","author":"J.F. Lynch","year":"1982","unstructured":"Lynch, J.F.: On sets of relations definable by addition. Journal of Symbolic Logic\u00a047, 659\u2013668 (1982)","journal-title":"Journal of Symbolic Logic"},{"key":"2_CR38","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/BF01276438","volume":"2","author":"J.F. Lynch","year":"1992","unstructured":"Lynch, J.F.: The quantifier structure of sentences that characterize nondeterministic time complexity. Computational Complexity\u00a02, 40\u201366 (1992)","journal-title":"Computational Complexity"},{"issue":"4","key":"2_CR39","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/BF01275490","volume":"3","author":"W. Maass","year":"1993","unstructured":"Maass, W., Schnitger, G., Szemer\u00e9di, E., Tur\u00e1n, G.: Two tapes versus one for off-line turing machines. Computational Complexity\u00a03(4), 392\u2013401 (1993)","journal-title":"Computational Complexity"},{"key":"2_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/BFb0028025","volume-title":"Computer Science Logic","author":"F. Olive","year":"1998","unstructured":"Olive, F.: A conjunctive logical characterization of nondeterministic linear time. In: Nielsen, M. (ed.) CSL 1997. LNCS, vol.\u00a01414, pp. 360\u2013372. Springer, Heidelberg (1998)"},{"key":"2_CR41","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1109\/SFCS.1983.39","volume-title":"24th Annual Symposium on Foundations of Computer Science","author":"W.J. Paul","year":"1983","unstructured":"Paul, W.J., Pippenger, N., Szemer\u00e9di, E., Trotter, W.T.: On determinism versus non-determinism and related problems (preliminary version). In: 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, November 7-9, pp. 429\u2013438. IEEE, Los Alamitos (1983)"},{"key":"2_CR42","doi-asserted-by":"crossref","unstructured":"Regan, K.: Machine models and linear time complexity. SIGACT News\u00a024(4) (Fall 1993)","DOI":"10.1145\/166589.166591"},{"key":"2_CR43","unstructured":"Ruhl, M.: Counting and addition cannot express deterministic transitive closure (1998)"},{"key":"2_CR44","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1145\/322047.322060","volume":"25","author":"C.P. Schnorr","year":"1978","unstructured":"Schnorr, C.P.: Satisfiability is quasilinear complete in NQL. Journal of the ACM\u00a025, 136\u2013145 (1978)","journal-title":"Journal of the ACM"},{"key":"2_CR45","doi-asserted-by":"crossref","unstructured":"Schwentick, T.: Graph connectivity and monadic NP. In: Proc. 35th IEEE Symp. on Foundations of Computer Science, pp. 614\u2013622 (1994)","DOI":"10.1109\/SFCS.1994.365730"},{"key":"2_CR46","unstructured":"Schwentick, T.: On winning Ehrenfeucht games and monadic NP. Doktorarbeit, Universit\u00e4t Mainz (1994)"},{"key":"2_CR47","doi-asserted-by":"crossref","unstructured":"Schwentick, T.: Graph connectivity, monadic NP and built-in relations of moderate degree. In: Proc. 22nd International Colloq. on Automata, Languages, and Programming, pp. 405\u2013416 (1995)","DOI":"10.1007\/3-540-60084-1_92"},{"key":"2_CR48","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0168-0072(95)00030-5","volume":"79","author":"T. Schwentick","year":"1996","unstructured":"Schwentick, T.: On winning Ehrenfeucht games and monadic NP. Annals of Pure and Applied Logic\u00a079, 61\u201392 (1996)","journal-title":"Annals of Pure and Applied Logic"},{"key":"2_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BFb0023481","volume-title":"STACS 97","author":"T. Schwentick","year":"1997","unstructured":"Schwentick, T.: Algebraic and logical characterizations of deterministic linear time classes. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol.\u00a01200, pp. 463\u2013474. Springer, Heidelberg (1997)"},{"key":"2_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/BFb0028031","volume-title":"Computer Science Logic","author":"T. Schwentick","year":"1998","unstructured":"Schwentick, T.: Padding and the expressive power of existential second-order logics. In: Nielsen, M. (ed.) CSL 1997. LNCS, vol.\u00a01414, pp. 461\u2013477. Springer, Heidelberg (1998)"},{"key":"2_CR51","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1007\/BFb0028580","volume-title":"STACS 98","author":"T. Schwentick","year":"1998","unstructured":"Schwentick, T., Barthelmann, K.: Local normal forms for _rst-order logic with applications to games and automata. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 444\u2013454. Springer, Heidelberg (1998)"},{"key":"2_CR52","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1109\/SWAT.1973.25","volume-title":"14th Annual Symposium on Switching and Automata Theory","author":"J.I. Seiferas","year":"1973","unstructured":"Seiferas, J.I., Fischer, M.J., Meyer, A.R.: Refinements of the nondeterministic time and space hierarchies. In: 14th Annual Symposium on Switching and Automata Theory, The University of Iowa, October 15-17, pp. 130\u2013137. IEEE, Los Alamitos (1973)"},{"key":"2_CR53","first-page":"179","volume-title":"Proceedings of the Sixth Annual Symposium on Switching Circuit Theory and Logical Design","author":"R.E. Stearns","year":"1965","unstructured":"Stearns, R.E., Hartmanis, J., Lewis II., P.M.: Hierarchies of memory limited computations. In: Proceedings of the Sixth Annual Symposium on Switching Circuit Theory and Logical Design, pp. 179\u2013190. IEEE, Los Alamitos (1965)"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/10703163_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,21]],"date-time":"2019-04-21T11:15:59Z","timestamp":1555845359000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/10703163_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540659228","9783540488552"],"references-count":53,"URL":"https:\/\/doi.org\/10.1007\/10703163_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999]]}}}