Mathematical Logic Quarterly 55 (3):245-258 (2009)

Abstract
This paper studies systems of explicit mathematics as introduced by Feferman [9, 11]. In particular, we propose weak explicit type systems with a restricted form of elementary comprehension whose provably terminating operations coincide with the functions on binary words that are computable in polynomial time. The systems considered are natural extensions of the first-order applicative theories introduced in Strahm [19, 20]
Keywords applicative theories  types and names  Feferman's explicit mathematics  feasible operations  theory
Categories No categories specified
(categorize this paper)
DOI 10.1002/malq.200810004
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 50,241
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Polynomial Time Operations in Explicit Mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
Polytime, Combinatory Logic and Positive Safe Induction.Cantini Andrea - 2002 - Archive for Mathematical Logic 41 (2):169-189.
Feasible Operations and Applicative Theories Based on Λη.Andrea Cantini - 2000 - Mathematical Logic Quarterly 46 (3):291-312.

Add more references

Citations of this work BETA

The Provably Terminating Operations of the Subsystem of Explicit Mathematics.Dieter Probst - 2011 - Annals of Pure and Applied Logic 162 (11):934-947.
Realisability in Weak Systems of Explicit Mathematics.Daria Spescha & Thomas Strahm - 2011 - Mathematical Logic Quarterly 57 (6):551-565.
Admissible Closures of Polynomial Time Computable Arithmetic.Dieter Probst & Thomas Strahm - 2011 - Archive for Mathematical Logic 50 (5-6):643-660.
A Feasible Theory of Truth Over Combinatory Algebra.Sebastian Eberhard - 2014 - Annals of Pure and Applied Logic 165 (5):1009-1033.

Add more citations

Similar books and articles

Polynomial Time Operations in Explicit Mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
Realisability in Weak Systems of Explicit Mathematics.Daria Spescha & Thomas Strahm - 2011 - Mathematical Logic Quarterly 57 (6):551-565.
The Provably Terminating Operations of the Subsystem of Explicit Mathematics.Dieter Probst - 2011 - Annals of Pure and Applied Logic 162 (11):934-947.
Safe Recursion with Higher Types and BCK-Algebra.Martin Hofmann - 2000 - Annals of Pure and Applied Logic 104 (1-3):113-166.
Power Types in Explicit Mathematics?Gerhard Jäger - 1997 - Journal of Symbolic Logic 62 (4):1142-1146.
The Analytic Polynomial-Time Hierarchy.Herbert Baier & Klaus W. Wagner - 1998 - Mathematical Logic Quarterly 44 (4):529-544.
Polynomial-Time Analogues of Isolatedness.Leon Harkleroad - 1992 - Annals of Pure and Applied Logic 56 (1-3):173-182.
Feasible Graphs and Colorings.Douglas Cenzer & Jeffrey Remmel - 1995 - Mathematical Logic Quarterly 41 (3):327-352.
Light Affine Lambda Calculus and Polynomial Time Strong Normalization.Kazushige Terui - 2007 - Archive for Mathematical Logic 46 (3-4):253-280.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
Machines Over the Reals and Non‐Uniformity.Felipe Cucker - 1997 - Mathematical Logic Quarterly 43 (2):143-157.

Analytics

Added to PP index
2013-12-01

Total views
14 ( #643,598 of 2,325,130 )

Recent downloads (6 months)
4 ( #224,998 of 2,325,130 )

How can I increase my downloads?

Downloads

My notes