- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
Higher type recursion, ramification and polynomial time
Annals of Pure and Applied Logic 104 (1-3):17-30 (2000)
Abstract
It is shown how to restrict recursion on notation in all finite types so as to characterize the polynomial-time computable functions. The restrictions are obtained by using a ramified type structure, and by adding linear concepts to the lambda calculusOther Versions
No versions found
My notes
Similar books and articles
Safe recursion with higher types and BCK-algebra.Martin Hofmann - 2000 - Annals of Pure and Applied Logic 104 (1-3):113-166.
Bounded arithmetic for NC, ALogTIME, L and NL.P. Clote & G. Takeuti - 1992 - Annals of Pure and Applied Logic 56 (1-3):73-117.
Bounded iteration and unary functions.Stefano Mazzanti - 2005 - Mathematical Logic Quarterly 51 (1):89-94.
Characterizing PSPACE with pointers.Isabel Oitavern - 2008 - Mathematical Logic Quarterly 54 (3):323-329.
Tailoring recursion for complexity.Erich Grädel & Yuri Gurevich - 1995 - Journal of Symbolic Logic 60 (3):952-969.
Feasible graphs with standard universe.Douglas Cenzer & Jeffrey B. Remmel - 1998 - Annals of Pure and Applied Logic 94 (1-3):21-35.
Applicative theories for the polynomial hierarchy of time and its levels.Reinhard Kahle & Isabel Oitavem - 2013 - Annals of Pure and Applied Logic 164 (6):663-675.
Control structures in programs and computational complexity.Karl-Heinz Niggl - 2005 - Annals of Pure and Applied Logic 133 (1-3):247-273.
Inductive types and type constraints in the second-order lambda calculus.Nax Paul Mendler - 1991 - Annals of Pure and Applied Logic 51 (1-2):159-172.
On the computability of fractal dimensions and Hausdorff measure.Ker-I. Ko - 1998 - Annals of Pure and Applied Logic 93 (1-3):195-216.
Analytics
Added to PP
2014-01-16
Downloads
73 (#302,861)
6 months
7 (#538,021)
2014-01-16
Downloads
73 (#302,861)
6 months
7 (#538,021)
Historical graph of downloads
Citations of this work
Safe recursion with higher types and BCK-algebra.Martin Hofmann - 2000 - Annals of Pure and Applied Logic 104 (1-3):113-166.
Light affine lambda calculus and polynomial time strong normalization.Kazushige Terui - 2007 - Archive for Mathematical Logic 46 (3-4):253-280.
Control structures in programs and computational complexity.Karl-Heinz Niggl - 2005 - Annals of Pure and Applied Logic 133 (1-3):247-273.
References found in this work
Über eine bisher noch nicht benützte erweiterung Des finiten standpunktes.Von Kurt Gödel - 1958 - Dialectica 12 (3‐4):280-287.
The realm of primitive recursion.Harold Simmons - 1988 - Archive for Mathematical Logic 27 (2):177-188.
Stephen Bellantoni and Stephen Cook. A new recursion-theoretic characterization of the polytime functions. Computational complexity, vol. 2 , pp. 97–110. - Arnold Beckmann and Andreas Weiermann. A term rewriting characterization of the polytime functions and related complexity classes. Archive for mathematical logic, vol. 36 , pp. 11–30. [REVIEW]Karl-Heinz Niggl - 2000 - Bulletin of Symbolic Logic 6 (3):351-353.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-99fc7d78b-s277s uwo