Bounded iteration and unary functions

Mathematical Logic Quarterly 51 (1):89-94 (2005)
  Copy   BIBTEX

Abstract

The set of unary functions of complexity classes defined by using bounded primitive recursion is inductively characterized by means of bounded iteration. Elementary unary functions, linear space computable unary functions and polynomial space computable unary functions are then inductively characterized using only composition and bounded iteration

Categories

Keywords

Reprint years

DOI

10.1002/malq.200410010

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,219

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

Iteration on notation and unary functions.Stefano Mazzanti - 2013 - Mathematical Logic Quarterly 59 (6):415-434.
Iterative Characterizations of Computable Unary Functions: A General Method.Stefano Mazzanti - 1997 - Mathematical Logic Quarterly 43 (1):29-38.
Uniformly computable aspects of inner functions: estimation and factorization.Timothy H. McNicholl - 2008 - Mathematical Logic Quarterly 54 (5):508-518.
Admissible closures of polynomial time computable arithmetic.Dieter Probst & Thomas Strahm - 2011 - Archive for Mathematical Logic 50 (5):643-660.
Derivatives of Computable Functions.Ning Zhong - 1998 - Mathematical Logic Quarterly 44 (3):304-316.
A feasible theory for analysis.Fernando Ferreira - 1994 - Journal of Symbolic Logic 59 (3):1001-1011.
Tailoring recursion for complexity.Erich Grädel & Yuri Gurevich - 1995 - Journal of Symbolic Logic 60 (3):952-969.
Consistency statements and iterations of computable functions in IΣ1 and PRA.Joost J. Joosten - 2010 - Archive for Mathematical Logic 49 (7-8):773-798.
Unary primitive recursive functions.Daniel E. Severin - 2008 - Journal of Symbolic Logic 73 (4):1122-1138.
Computability of measurable sets via effective topologies.Yongcheng Wu & Decheng Ding - 2006 - Archive for Mathematical Logic 45 (3):365-379.
Computability & unsolvability.Martin Davis - 1958 - New York: Dover Publications.
The elementary computable functions over the real numbers: applying two new techniques. [REVIEW]Manuel L. Campagnolo & Kerry Ojakian - 2008 - Archive for Mathematical Logic 46 (7-8):593-627.
Witnessing functions in bounded arithmetic and search problems.Mario Chiari & Jan Krajíček - 1998 - Journal of Symbolic Logic 63 (3):1095-1115.
Elementary realizability.Zlatan Damnjanovic - 1997 - Journal of Philosophical Logic 26 (3):311-339.
Polynomially Bounded Recursive Realizability.Saeed Salehi - 2005 - Notre Dame Journal of Formal Logic 46 (4):407-417.

Analytics

Added to PP
2013-12-01

Downloads
12 (#1,025,624)

6 months
5 (#544,079)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Iteration on notation and unary functions.Stefano Mazzanti - 2013 - Mathematical Logic Quarterly 59 (6):415-434.
Unary primitive recursive functions.Daniel E. Severin - 2008 - Journal of Symbolic Logic 73 (4):1122-1138.
Distributive proper forcing axiom and cardinal invariants.Huiling Zhu - 2013 - Archive for Mathematical Logic 52 (5-6):497-506.

Add more citations

References found in this work

No references found.

Add more references