Applicative theories for the polynomial hierarchy of time and its levels

&
Annals of Pure and Applied Logic 164 (6):663-675 (2013)
  Copy   BIBTEX

Abstract

In this paper we introduce applicative theories which characterize the polynomial hierarchy of time and its levels. These theories are based on a characterization of the functions in the polynomial hierarchy using monotonicity constraints, introduced by Ben-Amram, Loff, and Oitavem

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2012.05.006

Other Versions

No versions found

Links

PhilArchive



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

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

Feasible Operations and Applicative Theories Based on λη.Andrea Cantini - 2000 - Mathematical Logic Quarterly 46 (3):291-312.
Elementary explicit types and polynomial time operations.Daria Spescha & Thomas Strahm - 2009 - Mathematical Logic Quarterly 55 (3):245-258.
Relating the bounded arithmetic and polynomial time hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.
Polynomial time operations in explicit mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
Bounded arithmetic for NC, ALogTIME, L and NL.P. Clote & G. Takeuti - 1992 - Annals of Pure and Applied Logic 56 (1-3):73-117.
Review: Thomas Strahm, Polynomial Time Operations in Explicit Mathematics ; Andrea Cantini, Feasible Operations and Applicative Theories Based on $\lambda \eta $. [REVIEW]Fernando Ferreira - 2002 - Bulletin of Symbolic Logic 8 (4):534-535.
The Analytic Polynomial-Time Hierarchy.Herbert Baier & Klaus W. Wagner - 1998 - Mathematical Logic Quarterly 44 (4):529-544.
The polynomial hierarchy for some structures over the binary words.Herwig Nübling - 2007 - Mathematical Logic Quarterly 53 (1):43-51.
The Woods–Erdös conjecture for polynomial rings.Maxim Vsemirnov - 2001 - Annals of Pure and Applied Logic 113 (1-3):331-344.
Higher type recursion, ramification and polynomial time.Stephen J. Bellantoni, Karl-Heinz Niggl & Helmut Schwichtenberg - 2000 - Annals of Pure and Applied Logic 104 (1-3):17-30.

Analytics

Added to PP
2013-12-12

Downloads
37 (#611,759)

6 months
9 (#492,507)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Reinhard Kahle
University Tübingen

Citations of this work

Add more citations

References found in this work

Totality in applicative theories.Gerhard Jäger & Thomas Strahm - 1995 - Annals of Pure and Applied Logic 74 (2):105-120.
Foundations of Constructive Mathematics.Michael J. Beeson - 1987 - Studia Logica 46 (4):398-399.
The provably terminating operations of the subsystem of explicit mathematics.Dieter Probst - 2011 - Annals of Pure and Applied Logic 162 (11):934-947.
Elementary explicit types and polynomial time operations.Daria Spescha & Thomas Strahm - 2009 - Mathematical Logic Quarterly 55 (3):245-258.

View all 12 references / Add more references