{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T07:09:29Z","timestamp":1791097769638,"version":"4.1.0"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2002,1]]},"abstract":"<jats:p>This article presents two algebraic characterizations and two related complete problems for the complexity class DLIN that was introduced in [E. Grandjean, Ann. Math. Artif. Intell., 16 (1996), pp. 183--236]. DLIN is essentially the class of all functions that can be computed in linear time on a Random Access Machine which uses only numbers of linear value during its computations.<\/jats:p>\n                  <jats:p>The algebraic characterizations are in terms of recursion schemes that define unary functions. One of these schemes defines several functions simultaneously, while the other one defines only one function. From the algebraic characterizations, we derive two complete problems for DLIN under new, very strict, and machine-independent affine reductions.<\/jats:p>","DOI":"10.1137\/s0097539799360240","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"196-230","source":"Crossref","is-referenced-by-count":12,"title":["Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time"],"prefix":"10.1137","volume":"32","author":[{"given":"Etienne","family":"Grandjean","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Stephen Bellantoni, Predicative recursion and the polytime hierarchy, Progr. Comput. Sci. Appl. Logic, Vol. 13, Birkh\u00e4user Boston, Boston, MA, 1995, 15\u20132996c:68053","DOI":"10.1007\/978-1-4612-2566-9_2"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01201998"},{"key":"R3","unstructured":"S. Bloch, J. Buss, and J. Goldsmith,\n                      Sharply Bounded Alternation within P\n                      , Tech. report TR96\u2010011, Electronic Colloquium on Computational Complexity, 1996, available online from http:\/\/ftp.eccc.uni\u2010trier.de\/pub\/eccc\/reports\/1996\/TR96\u2010011\/index.html."},{"key":"R4","unstructured":"Alan Cobham, The intrinsic computational difficulty of functions, North\u2010Holland, Amsterdam, 1965, 24\u20133034:7376"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90080-L"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90063-N"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(84)90014-1"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3084"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"H.\u2010D. Ebbinghaus and J. Flum,\n                      Finite Model Theory\n                      , 2nd ed., Springer\u2010Verlag, Berlin, 1995.","DOI":"10.1007\/3-540-28788-4"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Ronald Fagin, Easier ways to win logical games, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 31, Amer. Math. Soc., Providence, RI, 1997, 1\u20133298d:03046","DOI":"10.1090\/dimacs\/031\/01"},{"key":"R11","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054190000217"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90149-A"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.2307\/2275767"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0217050"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0219028"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205055"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791223206"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02127798"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Etienne Grandjean, Fr\u00e9d\u00e9ric Olive, Monadic logical definability of NP\u2010complete problems, Lecture Notes in Comput. Sci., Vol. 933, Springer, Berlin, 1995, 190\u201320498f:68098","DOI":"10.1007\/BFb0022256"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001594"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Y. Gurevich,\n                      Algebras of feasible functions\n                      , in Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1983, pp. 210\u2013214.","DOI":"10.1109\/SFCS.1983.5"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Y. Gurevich and S. Shelah,\n                      Nearly linear time\n                      , in Logic at Botik \u201989, Lecture Notes in Comput. Sci. 363, A. Meyer and M. Taitslin, eds., Springer\u2010Verlag, New York, 1989, pp. 108\u2013118.","DOI":"10.1007\/3-540-51237-3_10"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80029-8"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"R. Karp,\n                      Reducibility among combinatorial problems\n                      , in Complexity of Computer Computations, Plenum Press, New York, 1972, pp. 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"Clemens Lautemann, Nicole Schweikardt, Thomas Schwentick, A logical characterisation of linear time on nondeterministic Turing machines, Lecture Notes in Comput. Sci., Vol. 1563, Springer, Berlin, 1999, 143\u20131522000i:68068","DOI":"10.1007\/3-540-49116-3_13"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"Clemens Lautemann, Bernhard Weinzinger, MonadicNLIN and quantifier\u2010free reductions, Lecture Notes in Comput. Sci., Vol. 1683, Springer, Berlin, 1999, 322\u20133372002e:68037","DOI":"10.1007\/3-540-48168-0_23"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"Daniel Leivant, Ramified recurrence and computational complexity. I. Word recurrence and poly\u2010time, Progr. Comput. Sci. Appl. Logic, Vol. 13, Birkh\u00e4user Boston, Boston, MA, 1995, 320\u201334396d:03059","DOI":"10.1007\/978-1-4612-2566-9_11"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Fr\u00e9d\u00e9ric Olive, A conjunctive logical characterization of nondeterministic linear time, Lecture Notes in Comput. Sci., Vol. 1414, Springer, Berlin, 1998, 360\u20133722000h:68086","DOI":"10.1007\/BFb0028025"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"W. J. Paul, N. Pippenger, E. Szemer\u00e9di, and W. T. Trotter,\n                      On determinism versus non\u2010determinism and related problems (preliminary version)\n                      , in Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science, Tucson, AZ, 1983, pp. 429\u2013438.","DOI":"10.1109\/SFCS.1983.39"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1145\/166589.166591"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"Klaus Reinhardt, Strict sequential P\u2010completeness, Lecture Notes in Comput. Sci., Vol. 1200, Springer, Berlin, 1997, 329\u201333898g:68052","DOI":"10.1007\/BFb0023470"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322060"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"Thomas Schwentick, Algebraic and logical characterizations of deterministic linear time classes, Lecture Notes in Comput. Sci., Vol. 1200, Springer, Berlin, 1997, 463\u201347498g:68053","DOI":"10.1007\/BFb0023481"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"Thomas Schwentick, Descriptive complexity, lower bounds and linear time, Lecture Notes in Comput. Sci., Vol. 1584, Springer, Berlin, 1999, 9\u2013282000g:68052","DOI":"10.1007\/10703163_2"},{"key":"R36","unstructured":", Proceedings of the fourteenth annual ACM symposium on theory of computing, Association for Computing Machinery (ACM), 1982, 0\u20130, v+408, Held in San Francisco, Calif., May 5\u20137, 198287g:68003"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539799360240","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:22Z","timestamp":1787336302000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539799360240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,1]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2002,1]]}},"alternative-id":["10.1137\/S0097539799360240"],"URL":"https:\/\/doi.org\/10.1137\/s0097539799360240","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,1]]}}}