Intuitionistic formal theories with realizability in subrecursive classes

Annals of Pure and Applied Logic 89 (1):3-15 (1997)
  Copy   BIBTEX

Abstract

A family of formal intuitionistic theories is proposed with realizability of proved formulas in several subrecursive classes, e.g. Grzegorczyk classes, polynomial-time computable functions class, etc. xA) Algorithm extraction forxyA is shown for various classes of bounded complexity. The results on polynomial computability are closely connected to work on the Bounded Arithmetic by S. Buss

Categories

Keywords

Reprint years

DOI

10.1016/s0168-0072(97)00002-x

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,225

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

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.
Preservation theorems for bounded formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
On the computational content of intuitionistic propositional proofs.Samuel R. Buss & Pavel Pudlák - 2001 - Annals of Pure and Applied Logic 109 (1-2):49-64.
Arithmetic complexity of the predicate logics of certain complete arithmetic theories.Valery Plisko - 2001 - Annals of Pure and Applied Logic 113 (1-3):243-259.
Polynomially Bounded Recursive Realizability.Saeed Salehi - 2005 - Notre Dame Journal of Formal Logic 46 (4):407-417.
On unsolvability in subrecursive classes of predicates.Forbes D. Lewis - 1979 - Notre Dame Journal of Formal Logic 20 (1):55-67.
On parallel hierarchies and Rki.Stephen Bloch - 1997 - Annals of Pure and Applied Logic 89 (2-3):231-273.
Functional interpretations of feasibly constructive arithmetic.Stephen Cook & Alasdair Urquhart - 1993 - Annals of Pure and Applied Logic 63 (2):103-200.
Structural complexity of.Dmitry Itsykson - 2010 - Annals of Pure and Applied Logic 162 (3):213-223.

Analytics

Added to PP
2014-01-16

Downloads
26 (#851,330)

6 months
9 (#482,469)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Some Classes of Recursive Functions.Andrzej Grzegorczyk - 1955 - Journal of Symbolic Logic 20 (1):71-72.

Add more references