Inhomogeneity of the p-s-Degrees of Recursive Functions

Mathematical Logic Quarterly 46 (3):385-392 (2000)

Abstract
The structure of the p-s-degrees of recursive functions is shown to be inhomogeneous. There are two p-s-degrees a and b above 0 such that [0, a] is distributive and [0, b] is nondistributive. Moreover, we will investigate how the number of values of each function reflects on its degree
Keywords Homogeneity  Polynomial time degree
Categories (categorize this paper)
DOI 10.1002/1521-3870(200008)46:3<385::AID-MALQ385>3.0.CO;2-D
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 47,122
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
Degrees of Relative Provability.Mingzhong Cai - 2012 - Notre Dame Journal of Formal Logic 53 (4):479-489.
Weak Presentations of Computable Fields.Carl G. Jockusch & Alexandra Shlapentokh - 1995 - Journal of Symbolic Logic 60 (1):199 - 208.
Degrees Joining to 0'. [REVIEW]David B. Posner & Robert W. Robinson - 1981 - Journal of Symbolic Logic 46 (4):714 - 722.
The Ackermann Functions Are Not Optimal, but by How Much?H. Simmons - 2010 - Journal of Symbolic Logic 75 (1):289-313.
Kleene Index Sets and Functional M-Degrees.Jeanleah Mohrherr - 1983 - Journal of Symbolic Logic 48 (3):829-840.
Generalized Weak Presentations.Alexandra Shlapentokh - 2002 - Journal of Symbolic Logic 67 (2):787-819.
Polynomial Time Operations in Explicit Mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
On the R.E. Predecessors of D.R.E. Degrees.Shamil Ishmukhametov - 1999 - Archive for Mathematical Logic 38 (6):373-386.
Time Polynomial in Input or Output.Yuri Gurevich & Saharon Shelah - 1989 - Journal of Symbolic Logic 54 (3):1083-1088.

Analytics

Added to PP index
2013-12-01

Total views
7 ( #941,380 of 2,289,307 )

Recent downloads (6 months)
1 ( #842,814 of 2,289,307 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature