{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:07:55Z","timestamp":1787508475852,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540626169","type":"print"},{"value":"9783540683421","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0023481","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T02:06:33Z","timestamp":1132365993000},"page":"463-474","source":"Crossref","is-referenced-by-count":3,"title":["Algebraic and logical characterizations of deterministic linear time classes"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Schwentick","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,10]]},"reference":[{"key":"38_CR1","doi-asserted-by":"crossref","unstructured":"S. Bellantoni. Predicative recursion and the polytime hierarchy. In P. Clote and J.B. Remmel, editors, Feasible Mathematics II, pages 15\u201329. Birkh\u00e4user, 1995.","DOI":"10.1007\/978-1-4612-2566-9_2"},{"key":"38_CR2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01201998","volume":"2","author":"S. Bellantoni","year":"1992","unstructured":"S. Bellantoni and S. Cook. A new recursion-theoretic characterization of the polytime functions. Comp. Complexity, 2:97\u2013110, 1992.","journal-title":"Comp. Complexity"},{"key":"38_CR3","unstructured":"S.A. Bloch, J.F. Buss, and J. Goldsmith. Sharply bounded alternation within P. Technical Report TR96-011, Electronic Colloquium on Computational Complexity, 1996. http:\/\/ftp.eccc.uni-trier.de\/pub\/eccc\/reports\/1996\/TR96-011\/index.html."},{"key":"38_CR4","unstructured":"A. Cobham. The intrinsic computational complexity of functions. In Y. Bar-Hillel, editor, Proceedings of: Logic, Methodology, and the Philosophy of Science, pages 24\u201330. North-Holland, 1964."},{"key":"38_CR5","first-page":"241","volume":"87","author":"K. J. Compton","year":"1990","unstructured":"K. J. Compton and C. Laflamme. An algebra and a logic for NC1. Information and Control, 87:241\u2013263, 1990.","journal-title":"Information and Control"},{"key":"38_CR6","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":"38_CR7","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1142\/S0129054190000217","volume":"1","author":"E. Gr\u00e4del","year":"1990","unstructured":"E. Gr\u00e4del. On the notion of linear time computability. Int. J. Found. Comput. Sci., 1:295\u2013307, 1990.","journal-title":"Int. J. Found. Comput. Sci."},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del. The expressive power of second order horn logic. In Proc. 8th Symposium on Theoretical Aspects of Computer Science STACS 91, volume 480 of LNCS, pages 466\u2013477. Springer-Verlag, 1991.","DOI":"10.1007\/BFb0020821"},{"key":"38_CR9","doi-asserted-by":"crossref","first-page":"952","DOI":"10.2307\/2275767","volume":"60","author":"E. Gr\u00e4del","year":"1995","unstructured":"E. Gr\u00e4del and Y. Gurevich. Tailoring recursion for complexity. Journal of Symbolic Logic, 60:952\u2013969, 1995.","journal-title":"Journal of Symbolic Logic"},{"key":"38_CR10","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1137\/0217050","volume":"17","author":"E. Grandjean","year":"1988","unstructured":"E. Grandjean. A natural NP-complete problem with a nontrivial lower bound. SIAM Journal of Computing, 17:786\u2013809, 1988.","journal-title":"SIAM Journal of Computing"},{"key":"38_CR11","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1137\/0219028","volume":"19","author":"E. Grandjean","year":"1990","unstructured":"E. Grandjean. A nontrivial lower bound for an NP problem on automata. SIAM Journal of Computing, 19:438\u2013451, 1990.","journal-title":"SIAM Journal of Computing"},{"key":"38_CR12","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":"38_CR13","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":"38_CR14","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":"38_CR15","doi-asserted-by":"crossref","unstructured":"E. Grandjean and F. Olive. Monadic logical definability of NP-complete problems. submitted, 1996.","DOI":"10.1007\/BFb0022256"},{"key":"38_CR16","doi-asserted-by":"crossref","unstructured":"Y. Gurevich. Algebras of feasible functions. In Proc. 24th IEEE Symp. on Foundations of Computer Science, pages 210\u2013214, 1983.","DOI":"10.1109\/SFCS.1983.5"},{"key":"38_CR17","doi-asserted-by":"crossref","unstructured":"Y. Gurevich and S. Shelah. Nearly linear time. In A. Meyer and M. Taitslin, editors, Logic at Botik '89, Lecture Notes in Computer Science 363, pages 108\u2013118. Springer-Verlag, 1989.","DOI":"10.1007\/3-540-51237-3_10"},{"key":"38_CR18","doi-asserted-by":"crossref","unstructured":"D. Leivant. Ramified recurrence and computational complexity I: Word recurrence and poly-time. In P. Clote and J.B. Remmel, editors, Feasible Mathematics II, pages 320\u2013343. Birkh\u00e4user, 1995.","DOI":"10.1007\/978-1-4612-2566-9_11"},{"key":"38_CR19","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/166589.166591","volume":"24","author":"K. Regan","year":"1993","unstructured":"K. Regan. Machine models and linear time complexity. SIGACT News, 24:4, Fall 1993.","journal-title":"SIGACT News"},{"key":"38_CR20","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1145\/322047.322060","volume":"25","author":"C. P. Schnorr","year":"1978","unstructured":"C. P. Schnorr. Satisfiability is quasilinear complete in NQL. Journal of the ACM, 25:136\u2013145, 1978.","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","STACS 97"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0023481","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T21:31:59Z","timestamp":1586554319000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0023481"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540626169","9783540683421"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/bfb0023481","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997]]}}}