Mathematical Logic Quarterly 44 (3):417-426 (1998)

Abstract
We define a fragment of Primitive Recursive Arithmetic by replacing the defining axioms for primitive recursive functions by those for functions in some specific complexity class. In this note we consider such theory for AC0. We present a model-theoretical property of this theory, by means of which we are able to characterize its provably total functions. Next we consider the problem of how strong the induction scheme can be in this theory
Keywords Bounded Arithmetic  LOGSPACE  Herbrand's Theorem  AC0
Categories (categorize this paper)
DOI 10.1002/malq.19980440312
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 53,558
Through your library

References found in this work BETA

Model Theory.Michael Makkai, C. C. Chang & H. J. Keisler - 1991 - Journal of Symbolic Logic 56 (3):1096.
On End‐Extensions of Models of ¬Exp.Fernando Ferreira - 1996 - Mathematical Logic Quarterly 42 (1):1-18.
Model Theory.Gebhard Fuhrken - 1976 - Journal of Symbolic Logic 41 (3):697-699.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Herbrand Consistency of Some Arithmetical Theories.Saeed Salehi - 2012 - Journal of Symbolic Logic 77 (3):807-827.
A Theory for Log-Space and NLIN Versus Co-NLIN.Chris Pollett - 2003 - Journal of Symbolic Logic 68 (4):1082-1090.
Remarks on Herbrand Normal Forms and Herbrand Realizations.Ulrich Kohlenbach - 1992 - Archive for Mathematical Logic 31 (5):305-317.
On Interpretations of Bounded Arithmetic and Bounded Set Theory.Richard Pettigrew - 2009 - Notre Dame Journal of Formal Logic 50 (2):141-152.
The Role of Parameters in Bar Rule and Bar Induction.Michael Rathjen - 1991 - Journal of Symbolic Logic 56 (2):715-730.
The Strength of Sharply Bounded Induction.Emil Jeřábek - 2006 - Mathematical Logic Quarterly 52 (6):613-624.
Herbrand's Theorem and Term Induction.Matthias Baaz & Georg Moser - 2005 - Archive for Mathematical Logic 45 (4):447-503.
Preservation Theorems for Bounded Formulas.Morteza Moniri - 2007 - Archive for Mathematical Logic 46 (1):9-14.
On Herbrand Consistency in Weak Arithmetic.Zofia Adamowicz & Paweł Zbierski - 2001 - Archive for Mathematical Logic 40 (6):399-413.
A Feasible Theory for Analysis.Fernando Ferreira - 1994 - Journal of Symbolic Logic 59 (3):1001-1011.
On the Scheme of Induction for Bounded Arithmetic Formulas.A. J. Wilkie & J. B. Paris - 1987 - Annals of Pure and Applied Logic 35 (3):261-302.

Analytics

Added to PP index
2014-01-16

Total views
10 ( #814,537 of 2,348,535 )

Recent downloads (6 months)
1 ( #512,295 of 2,348,535 )

How can I increase my downloads?

Downloads

My notes