{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:57:38Z","timestamp":1787500658030,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540656913","type":"print"},{"value":"9783540491163","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-49116-3_13","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T08:56:14Z","timestamp":1187254574000},"page":"143-152","source":"Crossref","is-referenced-by-count":4,"title":["A Logical Characterisation of Linear Time on Nondeterministic Turing Machines"],"prefix":"10.1007","author":[{"given":"Clemens","family":"Lautemann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicole","family":"Schweikardt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,4,12]]},"reference":[{"issue":"1","key":"13_CR1","doi-asserted-by":"publisher","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":"13_CR2","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/978-3-642-59136-5_3","volume":"2","author":"J. Autebert","year":"1997","unstructured":"J. Autebert, J. Berstel, and L. Boasson. Context-free languages and pushdown automata. Handbook of Formal Languages, 2:111\u2013174, 1997.","journal-title":"Handbook of Formal Languages"},{"key":"13_CR3","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01705890","volume":"4","author":"R. Book","year":"1970","unstructured":"R. Book and S. Greibach. Quasi-realtime languages. Math. Syst. Theory, 4:97\u2013111, 1970.","journal-title":"Math. Syst. Theory"},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"6","author":"J.R. B\u00fcchi","year":"1960","unstructured":"J.R. B\u00fcchi. Weak second-order arithmetic and finite automata. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 6:66\u201392, 1960.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"13_CR5","volume-title":"Finite Model Theory","author":"H.D. Ebbinghaus","year":"1995","unstructured":"H.D. Ebbinghaus and J. Flum. Finite Model Theory. Springer-Verlag, New York, 1995."},{"key":"13_CR6","unstructured":"R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In R.M. Karp, editor, Complexity of Computation, volume 7 of SIAM-Proceedings, pages 43\u201373. AMS, 1974."},{"key":"13_CR7","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(92)90149-A","volume":"101","author":"E. Gr\u00e4del","year":"1992","unstructured":"E. Gr\u00e4del. Capturing complexity classes by fragments of second order logic. Theoretical Computer Science, 101:35\u201357, 1992.","journal-title":"Theoretical Computer Science"},{"key":"13_CR8","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/BF01205055","volume":"4","author":"E. Grandjean","year":"1994","unstructured":"E. Grandjean. Invariance properties of RAMs and linear time. Computational Complexity, 4:62\u2013106, 1994.","journal-title":"Computational Complexity"},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1137\/S0097539791223206","volume":"23","author":"E. Grandjean","year":"1994","unstructured":"E. Grandjean. Linear time algorithms and NP-complete problems. SIAM Journal of Computing, 23:573\u2013597, 1994.","journal-title":"SIAM Journal of Computing"},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF02127798","volume":"16","author":"E. Grandjean","year":"1996","unstructured":"E. Grandjean. Sorting, linear time and the satisfiability problem. Annals of Mathematics and Artificial Intelligence, 16:183\u2013236, 1996.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"13_CR11","unstructured":"J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, 1979."},{"key":"13_CR12","volume-title":"Descriptive and Computational Complexity","author":"N. Immerman","year":"1998","unstructured":"N. Immerman. Descriptive and Computational Complexity. Springer-Verlag, New York, 1998."},{"key":"13_CR13","series-title":"Lect Notes Comput Sci","first-page":"205","volume-title":"Proceedings of the Annual Conference of the EACSL","author":"C. Lautemann","year":"1994","unstructured":"C. Lautemann, T. Schwentick, and D. Th\u00e9rien. Logics for context-free languages. In Proceedings of the Annual Conference of the EACSL, volume 933 of Lecture Notes in Computer Science, pages 205\u2013216, 1994."},{"key":"13_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":"13_CR15","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/BF01275490","volume":"3","author":"W. Maass","year":"1993","unstructured":"W. Maass, G. Schnitger, E. Szemer\u00e9di, and G. Tur\u00e1n. Two tapes versus one for off-line turing machines. Computational Complexity, 3:392\u2013401, 1993.","journal-title":"Computational Complexity"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"W. Paul, N. Pippenger, E. Szemer\u00e9di, and W. Trotter. On determinism versus nondeterminism and related problems. In Proc. 24th Ann. Symp. Found. Comput. Sci., pages 429\u2013438, 1983.","DOI":"10.1109\/SFCS.1983.39"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"T. Schwentick. Padding and the expressive power of existential second-order logics. In 11th Annual Conference of the EACSL, CSL\u2019 97, pages 461\u2013477, 1997.","DOI":"10.1007\/BFb0028031"}],"container-title":["Lecture Notes in Computer Science","STACS 99"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49116-3_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T00:43:02Z","timestamp":1556757782000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49116-3_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540656913","9783540491163"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-49116-3_13","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[1999]]}}}