{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T06:31:51Z","timestamp":1769927511340,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540600176","type":"print"},{"value":"9783540494041","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0022277","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T06:12:29Z","timestamp":1132639949000},"page":"486-500","source":"Crossref","is-referenced-by-count":28,"title":["Ramified recurrence and computational complexity II: Substitution and poly-space"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Leivant","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Yves","family":"Marion","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,15]]},"reference":[{"key":"35_CR1","first-page":"71","volume-title":"Fixpoint extensions of first-order logic and datalog-like languages","author":"S. Abiteboul","year":"1989","unstructured":"S. Abiteboul and V. Vianu. Fixpoint extensions of first-order logic and datalog-like languages. In Proceedings of the Fourth Annual Symposium on Logic in Computer Science, pages 71\u201379, Washington, D.C., 1989. IEEE Computer Society Press."},{"key":"35_CR2","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/0022-0000(91)90032-Z","volume":"43","author":"S. Abiteboul","year":"1991","unstructured":"S. Abiteboul and V. Vianu. Datalog extensions for database queries and updates. Journal of Computer and System Sciences, 43:62\u2013124, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"35_CR3","doi-asserted-by":"crossref","unstructured":"S. Abiteboul, E. Simon, and V. Vianu. Non-deterministic languages to express deterministic transformations. In Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1990.","DOI":"10.1145\/298514.298575"},{"key":"35_CR4","volume-title":"Foundations of Databases","author":"S. Abiteboul","year":"1994","unstructured":"S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, Reading, MA, 1994."},{"key":"35_CR5","doi-asserted-by":"crossref","unstructured":"Stephen Bellantoni and Stephen Cook. A new recursion-theoretic characterization of the poly-time functions, 1992.","DOI":"10.1145\/129712.129740"},{"key":"35_CR6","unstructured":"Stephen Bellantoni. Predicative Recursion and Computational Complexity. PhD thesis, University of Toronto, 1992."},{"key":"35_CR7","doi-asserted-by":"crossref","unstructured":"Stephen Bellantoni. Predicative recursion and the polytime hierarchy. In Peter Clote and Jeffery Remmel, editors, Feasible Mathematics II, Perspectives in Computer Science. Birkh\u00e4user, 1994.","DOI":"10.1007\/978-1-4612-2566-9_2"},{"key":"35_CR8","doi-asserted-by":"crossref","unstructured":"Stephen Bloch. Functional characterizations of uniform log-depth and polylogdepth circuit families. In Proceedings of the Seventh Annual Structure in Complexity Theory Conference, pages 193\u2013206. IEEE Computer Society Press, 1992.","DOI":"10.1109\/SCT.1992.215394"},{"key":"35_CR9","doi-asserted-by":"crossref","unstructured":"A.J. Bonner. Hypothetical datalog: complexity and expressibility. In Proceedings of the International Conference on Database Theory, volume 326 of LNCS, pages 144\u2013160, Berlin, 1988.","DOI":"10.1007\/3-540-50171-1_9"},{"key":"35_CR10","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"Ashok Chandra, Dexter Kozen, and Larry Stockmeyer. Alternation. Journal of the ACM, 28:114\u2013133, 1981.","journal-title":"Journal of the ACM"},{"key":"35_CR11","first-page":"24","volume-title":"The intrinsic computational difficulty of functions","author":"A. Cobham","year":"1965","unstructured":"A. Cobham. The intrinsic computational difficulty of functions. In Y. Bar-Hillel, editor, Proceedings of the International Conference on Logic, Methodology, and Philosophy of Science, pages 24\u201330. North-Holland, Amsterdam, 1965."},{"key":"35_CR12","unstructured":"R. Fagin. Generalized first order spectra and polynomial time recognizable sets. In R. Karp, editor, Complexity of Computation, pages 43\u201373. SIAM-AMS, 1974."},{"key":"35_CR13","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0304-3975(92)90363-K","volume":"100","author":"A. Goerdt","year":"1992","unstructured":"Andreas Goerdt. Characterizing complexity classes by higher-type primitive-recursive definitions. Theoretical Computer Science, 100:45\u201360, 1992. Preliminary version in: Proceedings of the Fourth IEEE Symposium on Logic in Computer Science, 1989, 364\u2013374.","journal-title":"Theoretical Computer Science"},{"key":"35_CR14","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0168-0072(86)90055-2","volume":"32","author":"Y. Gurevich","year":"1986","unstructured":"Y. Gurevich and S. Shelah. Fixed-point extensions of first-order logic. Annals of Pure and Applied Logic, 32:265\u2013280, 1986.","journal-title":"Annals of Pure and Applied Logic"},{"key":"35_CR15","doi-asserted-by":"crossref","unstructured":"Yuri Gurevich. Algebras of feasible functions. In Twenty Fourth Symposium on Foundations of Computer Science, pages 210\u2013214. IEEE Computer Society Press, 1983.","DOI":"10.1109\/SFCS.1983.5"},{"key":"35_CR16","unstructured":"W.G. Handley. Bellantoni and Cook's characterization of polynomial time functions. Typescript, August 1992."},{"key":"35_CR17","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/0022-0000(81)90039-8","volume":"22","author":"N. Immerman","year":"1981","unstructured":"Neil Immerman. Number of quantifiers is better than number of tape cells. Journal of Computer and System Sciences, 22:384\u2013406, 1981. Preminary version in Proceedings of the 20th IEE Symposium on Foundations of Computer Science (1979), 337\u2013347.","journal-title":"Journal of Computer and System Sciences"},{"key":"35_CR18","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/0022-0000(82)90011-3","volume":"25","author":"N. Immerman","year":"1982","unstructured":"N. Immerman. Upper and lower bounds for first-order expressibility. Journal of Computer and System Sciences, 25:76\u201398, 1982. Preliminary version in focs81, 74\u201382.","journal-title":"Journal of Computer and System Sciences"},{"key":"35_CR19","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"N. Immerman. Relational queries computable in polynomial time. Information and Control, 68:86\u2013104, 1986. Preliminary report in Fourteenth ACM Symposium on Theory of Computing, 1982, pp. 147\u2013152.","journal-title":"Information and Control"},{"key":"35_CR20","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman. Languages that capture complexity classes. SIAM Journal of Computing, 16:760\u2013778, 1987.","journal-title":"SIAM Journal of Computing"},{"key":"35_CR21","unstructured":"Neil Immerman. Dspace[n k] = var[k + 1]. In Proc. 6th IEEE Symp. on Structure in Complexity Theory, pages 334\u2013340, 1991."},{"key":"35_CR22","doi-asserted-by":"crossref","first-page":"139","DOI":"10.2307\/2272354","volume":"39","author":"N.G. Jones","year":"1974","unstructured":"N.G. Jones and A.L. Selman. Turing machines and the spectra of first order formulas. Journal of Symbolic Logic, 39:139\u2013150, 1974.","journal-title":"Journal of Symbolic Logic"},{"key":"35_CR23","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0890-5401(90)90006-4","volume":"89","author":"D. Leivant","year":"1990","unstructured":"Daniel Leivant. Inductive definitions over finite structures. Information and Computation, 89:95\u2013108, 1990.","journal-title":"Information and Computation"},{"key":"35_CR24","doi-asserted-by":"crossref","unstructured":"Daniel Leivant. Subrecursion and lambda representation over free algebras. In Samuel Buss and Philip Scott, editors, Feasible Mathematics, Perspectives in Computer Science, pages 281\u2013291. Birkhauser-Boston, New York, 1990.","DOI":"10.1007\/978-1-4612-3466-1_16"},{"key":"35_CR25","volume-title":"Conference Record of the Twentieth Annual ACM Symposium on Principles of Programming Languages","author":"D. Leivant","year":"1993","unstructured":"Daniel Leivant. Stratified functional programs and computational complexity. In Conference Record of the Twentieth Annual ACM Symposium on Principles of Programming Languages, New York, 1993. ACM."},{"key":"35_CR26","series-title":"LNCS #813","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/3-540-58140-5_23","volume-title":"Logical Foundations of Computer Science","author":"D. Leivant","year":"1994","unstructured":"Daniel Leivant. Predicative recurrence in finite type. In A. Nerode and Yu.V. Matiyasevich, editors, Logical Foundations of Computer Science, LNCS #813, pages 227\u2013239, Berlin, 1994. Springer-Verlag. Proceedings of the Third LFCS Symposium, St. Petersburg."},{"key":"35_CR27","doi-asserted-by":"crossref","unstructured":"Daniel Leivant. Ramified recurrence and computational complexity I: Word recurrence and poly-time. In Peter Clote and Jeffrey Remmel, editors, Feasible Mathematics II. Birkhauser-Boston, New York, 1994.","DOI":"10.1007\/978-1-4612-2566-9_11"},{"key":"35_CR28","volume-title":"Lecture notes in Mathematics","author":"Y. Moschovakis","year":"1983","unstructured":"Yiannis Moschovakis. Abstract recursion as the foundation for a theory of algorithms. In Computation and Proof Theory (Proceedings of the ASL Meeting in Aachen, 1983), Lecture notes in Mathematics, Berlin, 1983. Springer Verlag."},{"key":"35_CR29","unstructured":"Anhlan P. Nguyen. A formal system for linear space reasoning. PhD thesis, University of Toronto, 1993. Master of Science Thesis."},{"key":"35_CR30","doi-asserted-by":"crossref","unstructured":"J. Otto. V-comprehensions and P space. Preprint, 1995.","DOI":"10.1007\/3-540-60164-3_29"},{"key":"35_CR31","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1090\/S0002-9947-1963-0158822-2","volume":"106","author":"R.W. Ritchie","year":"1963","unstructured":"R.W. Ritchie. Classes of predictably computable functions. Trans. A.M.S., 106:139\u2013173, 1963.","journal-title":"Trans. A.M.S."},{"key":"35_CR32","volume-title":"Subrecursion","author":"H.E. Rose","year":"1984","unstructured":"H.E. Rose. Subrecursion. Clarendon Press (Oxford University Press), Oxford, 1984."},{"key":"35_CR33","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/BF01620765","volume":"27","author":"H. Simmons","year":"1988","unstructured":"Harold Simmons. The realm of primitive recursion. Archive for Mathematical Logic, 27:177\u2013, 1988.","journal-title":"Archive for Mathematical Logic"},{"key":"35_CR34","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BF01200263","volume":"30","author":"I. A. Stewart","year":"1993","unstructured":"Iain A. Stewart. Logical and semantic characterization of complexity classes. Acta Informatica, 30:61\u201387, 1993.","journal-title":"Acta Informatica"},{"key":"35_CR35","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01706069","volume":"6","author":"D.B. Thompson","year":"1972","unstructured":"D.B. Thompson. Subrecursiveness: machine independent notions of computability in restricted time and storage. Math. System Theory, 6:3\u201315, 1972.","journal-title":"Math. System Theory"},{"key":"35_CR36","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0304-3975(88)90052-7","volume":"60","author":"J. Tiuryn","year":"1988","unstructured":"J. Tiuryn and P. Urzyczyn. Some relationships between logics of programs and complexity theory. Theoretical Computer Science, 60:83\u2013108, 1988.","journal-title":"Theoretical Computer Science"},{"key":"35_CR37","volume-title":"CWI Monographs No. 6","author":"J.V. Tucker","year":"1988","unstructured":"J.V. Tucker and J.I. Zucker. Program Correctness over Abstract Data Types, with Error-State Semantics. CWI Monographs No. 6. North-Holland and the Centre for Mathematics and Computer Science, Amsterdam, 1988."},{"key":"35_CR38","first-page":"137","volume-title":"Fourteenth Symposium on Theory of Computing","author":"M. Vardi","year":"1982","unstructured":"M. Vardi. Complexity and relational query languages. In Fourteenth Symposium on Theory of Computing, pages 137\u2013146. ACM, New York, 1982."},{"issue":"2","key":"35_CR39","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1016\/0022-0000(83)90008-9","volume":"26","author":"K.N. Venkataraman","year":"1983","unstructured":"K.N. Venkataraman, Ann Yasuhara, and Frank M. Hawrusik. A view of computability on term algebras. Journal of Computer and System Sciences, 26(2):410\u2013471, June 1983.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0022277","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T02:43:08Z","timestamp":1586572988000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0022277"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540600176","9783540494041"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/bfb0022277","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]}}}