{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T08:58:12Z","timestamp":1762505892317},"publisher-location":"Berlin, Heidelberg","reference-count":27,"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_84","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:50:13Z","timestamp":1330278613000},"page":"177-194","source":"Crossref","is-referenced-by-count":24,"title":["Intrinsic theories and computational complexity"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Leivant","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"9_CR1","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":"9_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-68952-9","volume-title":"Foundations of Constructive Mathematics","author":"M. Beeson","year":"1985","unstructured":"Michael Beeson. Foundations of Constructive Mathematics. Springer-Verlag, Berlin, 1985."},{"key":"9_CR3","doi-asserted-by":"crossref","first-page":"122","DOI":"10.2307\/2275512","volume":"60","author":"R. Chuaqui","year":"1995","unstructured":"Roland Chuaqui and Patrick Suppes. Free-variable axiomatic foundations of infinitesimal analysis: a fragment with finitary consistency proof. Journal of Symbolic Logic, 60:122\u2013159, 1995.","journal-title":"Journal of Symbolic Logic"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Solomon Feferman. Definedness, 1995. Preprint.","DOI":"10.1007\/BF01135376"},{"key":"9_CR5","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BFb0103100","volume-title":"Higher Set Theory","author":"H. Friedman","year":"1978","unstructured":"H. Friedman. Classically and intuitionistically provable recursive functions. In G. H. Muller and D. S. Scott, editors, Higher Set Theory, pages 21\u201328. North-Holland, Amsterdam, 1978."},{"key":"9_CR6","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1111\/j.1746-8361.1958.tb01464.x","volume":"12","author":"K. G\u00f6del","year":"1958","unstructured":"Kurt G\u00f6del. \u00dcber eine bisher noch nicht benutzte erweiterung des finiten standpunktes. Dialectica, 12:280\u2013287, 1958.","journal-title":"Dialectica"},{"key":"9_CR7","volume-title":"From Frege to G\u00f6del, A Source Book in Mathematical Logic, 1879\u20131931","author":"J. Heijenoort van","year":"1967","unstructured":"J.van Heijenoort. From Frege to G\u00f6del, A Source Book in Mathematical Logic, 1879\u20131931. Harvard University Press, Cambridge, MA, 1967."},{"key":"9_CR8","first-page":"479","volume-title":"To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism","author":"W. A. Howard","year":"1980","unstructured":"W. A. Howard. The formulae-as-types notion of construction. In J. P. Seldin and J. R. Hindley, editors, To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, pages 479\u2013490. Academic Press, New York, 1980. Preliminary manuscript: 1969."},{"key":"9_CR9","volume-title":"Philosophical applications of free logic","author":"K. Lambert","year":"1991","unstructured":"K. Lambert. Introduction. In K. Lambert, editor, Philosophical applications of free logic, Oxford and New York, 1991. Oxford University Press."},{"key":"9_CR10","first-page":"460","volume-title":"Reasoning about functional programs and complexity classes associated with type disciplines","author":"D. Leivant","year":"1983","unstructured":"Daniel Leivant. Reasoning about functional programs and complexity classes associated with type disciplines. In Proceedings of the Twenty Fourth Annual Symposium on the Foundations of Computer Science, pages 460\u2013469, Washington, 1983. IEEE Computer Society."},{"key":"9_CR11","doi-asserted-by":"crossref","first-page":"682","DOI":"10.2307\/2274322","volume":"50","author":"D. Leivant","year":"1985","unstructured":"Daniel Leivant. Syntactic translations and provably recursive functions. Journal of Symbolic Logic, 50:682\u2013688, 1985.","journal-title":"Journal of Symbolic Logic"},{"key":"9_CR12","first-page":"279","volume-title":"Logic and Computer Science","author":"D. Leivant","year":"1990","unstructured":"Daniel Leivant. Contracting proofs to programs. In P. Odifreddi, editor, Logic and Computer Science, pages 279\u2013327. Academic Press, London, 1990."},{"key":"9_CR13","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/978-1-4612-3466-1_16","volume-title":"Feasible Mathematics, Perspectives in Computer Science","author":"D. Leivant","year":"1990","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."},{"key":"9_CR14","first-page":"295","volume-title":"Logic from Computer Science","author":"D. Leivant","year":"1991","unstructured":"Daniel Leivant. Semantic characterization of number theories. In Y. Moschovakis, editor, Logic from Computer Science, pages 295\u2013318. Springer-Verlag, New York, 1991."},{"key":"9_CR15","first-page":"227","volume-title":"LNCS","author":"D. Leivant","year":"1994","unstructured":"D. Leivant. Predicative recurrence in finite type. In A. Nerode and Yu.V. Matiyasevich, editors, Logical Foundations of Computer Science (Third International Symposium), LNCS, pages 227\u2013239, Berlin, 1994. Springer-Verlag."},{"key":"9_CR16","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1006\/inco.1994.1038","volume":"110","author":"D. Leivant","year":"1994","unstructured":"Daniel Leivant. A foundational delineation of poly-time. Information and Computation, 110:391\u2013420, 1994. (Special issue of selected papers from LICS'91, edited by G. Kahn). Preminary report: A foundational delineation of computational feasibility, in Proceedings of the Sixth IEEE Conference on Logic in Computer Science, IEEE Computer Society Press, 1991.","journal-title":"Information and Computation"},{"key":"9_CR17","first-page":"320","volume-title":"Feasible Mathematics II, Perspectives in Computer Science","author":"D. Leivant","year":"1994","unstructured":"Daniel Leivant. Ramified recurrence and computational complexity I: Word recurrence and poly-time. In Peter Clote and Jeffrey Remmel, editors, Feasible Mathematics II, Perspectives in Computer Science, pages 320\u2013343. Birkhauser-Boston, New York, 1994."},{"key":"9_CR18","doi-asserted-by":"crossref","DOI":"10.1515\/9781400858927","volume-title":"Predicative Arithmetic","author":"E. Nelson","year":"1986","unstructured":"Edward Nelson. Predicative Arithmetic. Princeton University Press, Princeton, 1986."},{"key":"9_CR19","first-page":"459","volume-title":"Intuitionism and Proof Theory","author":"C. Parsons","year":"1977","unstructured":"Charles Parsons. On a number-theoretic choice schema and its relation to induction. In A. Kino, J. Myhill, and R. Vesley, editors, Intuitionism and Proof Theory, pages 459\u2013473. North-Holland, Amsterdam, 1977."},{"key":"9_CR20","unstructured":"Giuseppe Peano. Arithmetices principia, novo methodo exposita. Torino, 1889. English translation in [Hei67], 83\u201397."},{"key":"9_CR21","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/S0049-237X(08)70849-8","volume-title":"Proceedings of the Second Scandinavian Logic Symposium","author":"D. Prawitz","year":"1971","unstructured":"Dag Prawitz. Ideas and results in proof theory. In J. E. Fenstad, editor, Proceedings of the Second Scandinavian Logic Symposium, pages 235\u2013307, Amsterdam, 1971. North-Holland."},{"key":"9_CR22","first-page":"192","volume":"395","author":"M. Presburger","year":"1929","unstructured":"M. Presburger. Ueber die Vollst\u00e4ndigkeit eines gewissen systems der arithmetik ganzer zahlen in welchem die addition als einzige operation hervortritt. In Comptes Rendues, Ier Congr\u00e8 des Math\u00e9matiques des Pays Salves, pages 192\u2013201, 395, Warsaw, 1929.","journal-title":"Comptes Rendues, Ier Congr\u00e8 des Math\u00e9matiques des Pays Salves"},{"key":"9_CR23","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/BF01448013","volume":"92","author":"M. Sch\u00f6nfinkel","year":"1924","unstructured":"M. Sch\u00f6nfinkel. \u00dcber die Bausteine der mathematischen Logik. Mathematische Annalen, 92:305\u2013316, 1924. English translation: On the building blocks of mathematical logic, in [Hei67], 355\u2013366.","journal-title":"Mathematische Annalen"},{"key":"9_CR24","first-page":"28","volume-title":"Bertrand Russell: Philosopher of the Century","author":"D. Scott","year":"1967","unstructured":"Dana Scott. Existence and description in formal logic. In Bertrand Russell: Philosopher of the Century, pages 28\u201348. Little, Brown and Co., Boston, 1967."},{"key":"9_CR25","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1007\/BFb0061839","volume-title":"Applications of sheaves, LNM 753","author":"D. Scott","year":"1979","unstructured":"Dana Scott. Identity and existence in formal logic. In Applications of sheaves, LNM 753, pages 660\u2013669. Springer-Verlag, Berlin, 1979."},{"key":"9_CR26","doi-asserted-by":"crossref","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\u2013188, 1988.","journal-title":"Archive for Mathematical Logic"},{"key":"9_CR27","volume-title":"Constructivism in Mathematics, an Introduction","author":"A. S. Troelstra","year":"1988","unstructured":"Anne S. Troelstra and Dirk van Dalen. Constructivism in Mathematics, an Introduction. North-Holland, Amsterdam, 1988. Two volumes."}],"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_84.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:55:46Z","timestamp":1605646546000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60178-3_84"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540601784","9783540447207"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-60178-3_84","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}