{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:15:35Z","timestamp":1725459335014},"publisher-location":"Berlin\/Heidelberg","reference-count":31,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540565175"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0037112","type":"book-chapter","created":{"date-parts":[[2006,1,25]],"date-time":"2006-01-25T10:21:36Z","timestamp":1138184496000},"page":"274-288","source":"Crossref","is-referenced-by-count":21,"title":["Lambda calculus characterizations of poly-time"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Leivant","sequence":"first","affiliation":[]},{"given":"Jean-Yves","family":"Marion","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"unstructured":"Hendrick P. Barendregt, The Lambda-Calculus: Its Syntax and Semantics, North-Holland, 1980.","key":"19_CR1"},{"key":"19_CR2","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0304-3975(85)90135-5","volume":"39","author":"B. Corrado","year":"1985","unstructured":"Corrado B\u00f6hm and Allessandro Berarducci, Automatic synthesis of typed \u03bb-programs on term algebras, Theoretical Computer Science 39 (1985) 135\u2013154.","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Stephen Bellantoni and Stephen Cook, A new recursion-theoretic characterization of the poly-time functions, to appear in Computational Complexity 1992.","key":"19_CR3","DOI":"10.1007\/BF01201998"},{"unstructured":"Stephen Bloch, Functional characterizations of uniform log-depth and polylog-depth circuit families, to appear in the Proceedings of the 1992 IEEE Conference on Structure in Complexity.","key":"19_CR4"},{"key":"19_CR5","volume-title":"Bounded Arithmetic","author":"S. Buss","year":"1986","unstructured":"Samuel Buss, Bounded Arithmetic, Bibliopolis, Naples, 1986."},{"key":"19_CR6","first-page":"24","volume-title":"Proceedings of the International Conference on Logic, Methodology, and Philosophy of Science","author":"A. Cobham","year":"1962","unstructured":"A. Cobham, The intrinsic computational difficulty of functions, in Y. Bar-Hillel (ed.), Proceedings of the International Conference on Logic, Methodology, and Philosophy of Science, North-Holland, Amsterdam (1962) 24\u201330."},{"key":"19_CR7","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1145\/322358.322370","volume":"30","author":"S. Fortune","year":"1983","unstructured":"Steven Fortune, Daniel Leivant, and Michael O'Donnell, The expressiveness of simple and second order type structures, Journal of the ACM 30 (1983), pp 151\u2013185.","journal-title":"Journal of the ACM"},{"key":"19_CR8","volume-title":"PhD Dissertation","author":"S. Fortune","year":"1979","unstructured":"Steven Fortune, Topics in Computational Complexity, PhD Dissertation, Cornell University, Ithaca, NY, 1979."},{"unstructured":"Jean-Yves Girard, Interpr\u00e9tation fonctionelle et \u00e9limination des coupures dans l'arithm\u00e9tique d'ordre superieur, Th\u00e8se de Doctorat d'Etat, 1972, Paris.","key":"19_CR9"},{"unstructured":"A. Grzegoczyk, Some classes of recursive functions, Rozprawy Mate. IV, Warsaw, 1953.","key":"19_CR10"},{"key":"19_CR11","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0168-0072(86)90055-2","volume":"32","author":"Y. Gurevich","year":"1986","unstructured":"Yuri Gurevich and Saharon Shelah, Fixed-point extensions of first-order logic, Annals of Pure and Applied Logic 32 (1986) 265\u2013280.","journal-title":"Annals of Pure and Applied Logic"},{"doi-asserted-by":"crossref","unstructured":"Yuri Gurevich, Algebras of feasible functions, Twenty Fourth Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1983, 210\u2013214.","key":"19_CR12","DOI":"10.1109\/SFCS.1983.5"},{"key":"19_CR13","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"Neil Immerman, Relational queries computable in polynomial time, Information and Control 68 (1986) 86\u2013104. Preliminary report in Fourteenth ACM Symposium on Theory of Computing (1982) 147\u2013152.","journal-title":"Information and Control"},{"key":"19_CR14","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"Neil Immerman, Languages which capture complexity classes, SIAM Journal of Computing 16 (1987) 760\u2013778.","journal-title":"SIAM Journal of Computing"},{"key":"19_CR15","series-title":"Perspectives in Computer Science","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/978-1-4612-3466-1_16","volume-title":"Feasible Mathematics","author":"D. Leivant","year":"1990","unstructured":"Daniel Leivant, Subrecursion and lambda representation over free algebras (Preliminary Summary), in Samuel Buss & Philip Scott (eds.), Feasible Mathematics, Perspectives in Computer Science, Birkhauser-Boston, New York (1990) 281\u2013291."},{"key":"19_CR16","doi-asserted-by":"crossref","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 (1990) 95\u2013108.","journal-title":"Information and Computation"},{"key":"19_CR17","volume-title":"A foundational delineation of computational feasiblity","author":"D. Leivant","year":"1991","unstructured":"Daniel Leivant, A foundational delineation of computational feasiblity, in Proceedings of the Sixth IEEE Conference on Logic in Computer Science (Amsterdam), IEEE Computer Society Press, Washington, D.C., 1991."},{"doi-asserted-by":"crossref","unstructured":"Daniel Leivant, Finitely stratified polymorphism, Information and Computation, 1991.","key":"19_CR18","DOI":"10.1016\/0890-5401(91)90053-5"},{"doi-asserted-by":"crossref","unstructured":"Daniel Leivant, A foundational delineation of poly-time, Information and Computation, 1993.","key":"19_CR19","DOI":"10.1006\/inco.1994.1038"},{"doi-asserted-by":"crossref","unstructured":"Daniel Leivant, Stratified functional programs and computational complexity, Conference Record of the Twentieth Annual ACM Symposium on Principles of Programming Languages, 1993.","key":"19_CR20","DOI":"10.1145\/158511.158659"},{"doi-asserted-by":"crossref","unstructured":"Harry Mairson, A simple proof of a theorem of Statman, to appear in Theoretical Computer Science, 1992.","key":"19_CR21","DOI":"10.1016\/0304-3975(92)90020-G"},{"key":"19_CR22","first-page":"176","volume-title":"A programming language theorem which is independent of Peano Arithemtic","author":"M. O'Donnell","year":"1979","unstructured":"Michael O'Donnell, A programming language theorem which is independent of Peano Arithemtic, Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, ACM, New York, 1979, 176\u2013188."},{"key":"19_CR23","first-page":"21","volume":"26","author":"C. Papadimitriou","year":"1985","unstructured":"Christos Papadimitriou, A note on the expressive power of PROLOG, Bull. EATCS 26 (June 1985) 21\u201323.","journal-title":"Bull. EATCS"},{"key":"19_CR24","volume-title":"Rekursive Funktionen","author":"R. P\u00e9ter","year":"1966","unstructured":"R\u00f3sza P\u00e9ter, Rekursive Funktionen, Akad\u00e9miai Kiad\u00f3, Budapest, 1966. English translation: Recursive Functions, Academic Press, New York, 1967."},{"key":"19_CR25","volume-title":"Natural Deduction","author":"D. Prawitz","year":"1965","unstructured":"Dag Prawitz, Natural Deduction, Almqvist and Wiskel, Uppsala, 1965."},{"key":"19_CR26","first-page":"408","volume-title":"Conference on Porgramming","author":"J. Reynolds","year":"1974","unstructured":"John Reynolds, Towards a theory of type structures, in J. Loeckx (ed.), Conference on Porgramming, Springer-Verlag (LNCS #19), Berlin, 1974, pp. 408\u2013425."},{"key":"19_CR27","first-page":"319","volume":"7","author":"V. Sazonov","year":"1980","unstructured":"Vladimir Sazonov, Polynomial computability and recursivity in finite domains, Electronische Informationsverarbeitung und Kybernetik 7 (1980) 319\u2013323.","journal-title":"Electronische Informationsverarbeitung und Kybernetik"},{"key":"19_CR28","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF02276799","volume":"17","author":"H. Schwichtenberg","year":"1976","unstructured":"Helmut Schwichtenberg, Definierbare Funktionen im Lambda-Kalkul mit Typen, Archiv f. Logik u. Grundlagenforsch. 17 (1976) 113\u2013114.","journal-title":"Archiv f. Logik u. Grundlagenforsch"},{"key":"19_CR29","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0304-3975(79)90007-0","volume":"9","author":"R. Statman","year":"1979","unstructured":"Richard Statman, The typed \u03bb-calculus is not elementary recursive, Theoretical Computer Science 9 (1979) 73\u201381.","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Moshe Vardi, Complexity and relational query languages, Fourteenth ACM Symposium on Theory of Computing (1982) 137\u2013146.","key":"19_CR30","DOI":"10.1145\/800070.802186"},{"doi-asserted-by":"crossref","unstructured":"Marek Zaionc, Word operations definable in typed \u03bb-calculus, Theoretical Computer Science 52 (1987).","key":"19_CR31","DOI":"10.1016\/0304-3975(87)90077-6"}],"container-title":["Lecture Notes in Computer Science","Typed Lambda Calculi and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0037112.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T17:22:05Z","timestamp":1607534525000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0037112"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540565175"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/bfb0037112","relation":{},"subject":[]}}