{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:13:27Z","timestamp":1725664407968},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540601784"},{"type":"electronic","value":"9783540447207"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60178-3_88","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:49:12Z","timestamp":1330260552000},"page":"253-268","source":"Crossref","is-referenced-by-count":4,"title":["Characterizing parallel time by type 2 recursions with polynomial output length"],"prefix":"10.1007","author":[{"given":"Stephen J.","family":"Bellantoni","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01201998","volume":"2","author":"S. Bellantoni","year":"1992","unstructured":"S. Bellantoni and S. Cook, \u201cA New Recursion-Theoretic Characterization of the Polytime Functions\u201d, computational complexity v. 2, p. 97\u2013110, 1992. Extended Abstract appeared in Proc. 24th Symposium on the Theory Of Computing, 1992.","journal-title":"computational complexity"},{"unstructured":"S. Bellantoni, \u201cPredicative Recursion and Computational Complexity\u201d, Ph.D. Thesis, Department of Computer Science, University of Toronto, 1992. Available as Technical Report 264\/92.","key":"13_CR2"},{"unstructured":"S. Bellantoni, \u201cFurther complexity characterizations using predicative recursion\u201d, submitted for publication.","key":"13_CR3"},{"doi-asserted-by":"crossref","unstructured":"S. Bloch, \u201cFunctional Characterizations of Uniform Log-depth and Polylog-depth Circuit Families\u201d, in Proceedings of the Seventh Annual Structure in Complexity Theory Conference, IEEE (1992).","key":"13_CR4","DOI":"10.1109\/SCT.1992.215394"},{"issue":"n.1","key":"13_CR5","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"A. Chandra, D. Kozen, L. Stockmeyer, \u201cAlternation\u201d, in Journal of the Association for Computing Machinery, v. 28, n. 1, p. 114\u2013133, Jan 1981.","journal-title":"Journal of the Association for Computing Machinery"},{"doi-asserted-by":"crossref","unstructured":"P. Clote, \u201cSequential, machine-independent characterizations of the parallel complexity classes ALogTime, AC k, NCk, and NC\u201d, in MSI Workshop on Feasible Mathematics, Birkhauser, 1989.","key":"13_CR6","DOI":"10.1007\/978-1-4612-3466-1_4"},{"key":"13_CR7","first-page":"24","volume-title":"The intrinsic computational difficulty of functions","author":"A. Cobham","year":"1964","unstructured":"A. Cobham, \u201cThe intrinsic computational difficulty of functions\u201d. In Y. Bar-Hillel ed., Proc. of the 1964 International Congress for Logic, Methodology, and the Philosophy of Science, p. 24\u201330. North Holland, Amsterdam, 1964."},{"key":"13_CR8","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman, \u201cLanguages That Capture Complexity Classes\u201d, SIAM Journal of Computing, p. 760\u2013778, v. 16 (1987).","journal-title":"SIAM Journal of Computing"},{"doi-asserted-by":"crossref","unstructured":"D. Leivant, \u201cSubrecursion and lambda representation over free algebras (Preliminary summary)\u201d, in Feasible Mathematics, S. Buss and P. Scott, eds., Birkhauser 1990.","key":"13_CR9","DOI":"10.1007\/978-1-4612-3466-1_16"},{"doi-asserted-by":"crossref","unstructured":"D. Leivant, \u201cRamified recurrence and computational complexity I: Word recurrence and poly-time\u201d, in Feasible Mathematics II, P. Clote and J. B. Remmell, eds., Birkhauser, 1995.","key":"13_CR10","DOI":"10.1007\/978-1-4612-2566-9_11"},{"unstructured":"D. Leivant, \u201cRamified recurrence and computational complexity III: Higher type recurrence and elementary complexity\u201d. Preliminary version appears in Logic From Computer Science 1994, Nerode and Matyasevich, eds., Lecture Notes in Computer Science, Springer Verlag.","key":"13_CR11"},{"doi-asserted-by":"crossref","unstructured":"D. Leivant, J. Y. Marion, \u201cRamified recurrence and computational complexity II: Substitution and poly-space\u201d, in Computer Science Logic, J. Tiuryn and L. Pacholsky, eds., Lecture Notes in Computer Science, Springer Verlag.","key":"13_CR12","DOI":"10.1007\/BFb0022277"},{"unstructured":"D. Leivant, J. Y. Marion, \u201cApplicative characterization of polyspace (extended summary)\u201d, Manuscript, 1994.","key":"13_CR13"},{"unstructured":"A. Nguyen, A Formal System for Linear-Space Reasoning, M.Sc. Thesis, Department of Computer Science, University of Toronto, 1993.","key":"13_CR14"},{"unstructured":"J. Otto, Tensor and Linear Time, Logic and Computational Complexity, D. Leivant, ed., Lecture Notes in Computer Science, Springer Verlag, 1995.","key":"13_CR15"},{"key":"13_CR16","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W. Ruzzo","year":"1981","unstructured":"W. Ruzzo, \u201cOn Uniform Circuit Complexity\u201d, Journal of Computer and System Sciences, v. 22, p. 365\u2013383, 1981.","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"H. Simmons, \u201cThe Realm of Primitive Recursion\u201d, Archive for Mathematical Logic, v. 27, p. 177+, Springer Verlag, 1988.","key":"13_CR17","DOI":"10.1007\/BF01620765"}],"container-title":["Lecture Notes in Computer Science","Logic and Computational Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60178-3_88.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:55:47Z","timestamp":1605628547000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60178-3_88"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540601784","9783540447207"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-60178-3_88","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}