Predicatively computable functions on sets

Archive for Mathematical Logic 54 (3-4):471-485 (2015)
  Copy   BIBTEX

Abstract

Inspired from a joint work by A. Beckmann, S. Buss and S. Friedman, we propose a class of set-theoretic functions, predicatively computable set functions. Each function in this class is polynomial time computable when we restrict to finite binary strings.

Categories

Keywords

Reprint years

DOI

10.1007/s00153-015-0422-2

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,612

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

A Simple Observation Regarding Iterations Of Finite-valued Polynomial-time Functions.Jerzy Mycka - 2009 - Reports on Mathematical Logic:19-29.
Time polynomial in input or output.Yuri Gurevich & Saharon Shelah - 1989 - Journal of Symbolic Logic 54 (3):1083-1088.
Computability of measurable sets via effective topologies.Yongcheng Wu & Decheng Ding - 2006 - Archive for Mathematical Logic 45 (3):365-379.
Limitwise monotonic functions, sets, and degrees on computable domains.Asher M. Kach & Daniel Turetsky - 2010 - Journal of Symbolic Logic 75 (1):131-154.
Chainable and circularly chainable semicomputable sets in computable topological spaces.Eugen Čičković, Zvonko Iljazović & Lucija Validžić - 2019 - Archive for Mathematical Logic 58 (7-8):885-897.
Bounded iteration and unary functions.Stefano Mazzanti - 2005 - Mathematical Logic Quarterly 51 (1):89-94.
Generalization of Shapiro’s theorem to higher arities and noninjective notations.Dariusz Kalociński & Michał Wrocławski - 2022 - Archive for Mathematical Logic 62 (1):257-288.
The algebraic structure of the isomorphic types of tally, polynomial time computable sets.Yongge Wang - 2002 - Archive for Mathematical Logic 41 (3):215-244.
Computable shuffle sums of ordinals.Asher M. Kach - 2008 - Archive for Mathematical Logic 47 (3):211-219.
On the convergence of Fourier series of computable Lebesgue integrable functions.Philippe Moser - 2010 - Mathematical Logic Quarterly 56 (5):461-469.

Analytics

Added to PP
2015-03-22

Downloads
28 (#138,667)

6 months
5 (#1,552,255)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Safe recursive set functions.Arnold Beckmann, Samuel R. Buss & Sy-David Friedman - 2015 - Journal of Symbolic Logic 80 (3):730-762.
Cobham recursive set functions.Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller & Neil Thapen - 2016 - Annals of Pure and Applied Logic 167 (3):335-369.

Add more citations

References found in this work

The fine structure of the constructible hierarchy.R. Björn Jensen - 1972 - Annals of Mathematical Logic 4 (3):229.
Safe recursive set functions.Arnold Beckmann, Samuel R. Buss & Sy-David Friedman - 2015 - Journal of Symbolic Logic 80 (3):730-762.

Add more references