Annals of Pure and Applied Logic 116 (1-3):273-295 (2002)
Abstract |
We study connections between strong reducibilities and properties of computably enumerable sets such as simplicity. We say that a class of computably enumerable sets bounded iff there is an m-incomplete computably enumerable set A such that every set in is m-reducible to A. For example, we show that the class of effectively simple sets is bounded; but the class of maximal sets is not. Furthermore, the class of computably enumerable sets Turing reducible to a computably enumerable set B is bounded iff B is low2. For r = bwtt,tt,wtt and T, there is a bounded class intersecting every computably enumerable r-degree; for r = c, d and p, no such class exists
|
Keywords | No keywords specified (fix it) |
Categories | (categorize this paper) |
DOI | 10.1016/s0168-0072(01)00114-2 |
Options |
![]() ![]() ![]() ![]() |
Download options
References found in this work BETA
Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 5 (7-13):117-125.
Creative Sets.John Myhill - 1955 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 1 (2):97-108.
Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Mathematical Logic Quarterly 5 (7‐13):117-125.
The Theory of the Recursively Enumerable Weak Truth-Table Degrees is Undecidable.Klaus Ambos-Spies, André Nies & Richard A. Shore - 1992 - Journal of Symbolic Logic 57 (3):864-874.
View all 9 references / Add more references
Citations of this work BETA
No citations found.
Similar books and articles
An Incomplete Set of Shortest Descriptions.Frank Stephan & Jason Teutsch - 2012 - Journal of Symbolic Logic 77 (1):291-307.
On Injective Enumerability of Recursively Enumerable Classes of Cofinite Sets.Stephan Wehner - 1995 - Archive for Mathematical Logic 34 (3):183-196.
On Σ1 1 Equivalence Relations with Borel Classes of Bounded Rank.Ramez L. Sami - 1984 - Journal of Symbolic Logic 49 (4):1273 - 1283.
On Recursive Enumerability with Finite Repetitions.Stephan Wehner - 1999 - Journal of Symbolic Logic 64 (3):927-945.
Enumerations of the Kolmogorov Function.Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan & Leen Torenvliet - 2006 - Journal of Symbolic Logic 71 (2):501 - 528.
Finite Automata, Real Time Processes and Counting Problems in Bounded Arithmetics.Mirosław Kutyłowski - 1988 - Journal of Symbolic Logic 53 (1):243-258.
First Order Properties on Nowhere Dense Structures.Nešetřil Jaroslav & Ossona De Mendez Patrice - 2010 - Journal of Symbolic Logic 75 (3):868-887.
First Order Properties on Nowhere Dense Structures.Jaroslav Nešetřil & Patrice Ossona de Mendez - 2010 - Journal of Symbolic Logic 75 (3):868 - 887.
Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
Bounded Scott Set Saturation.Alex M. McAllister - 2002 - Mathematical Logic Quarterly 48 (2):245-259.
Bounded Query Classes and the Difference Hierarchy.Richard Beigel, William I. Gasarch & Louise Hay - 1989 - Archive for Mathematical Logic 29 (2):69-84.
Analytics
Added to PP index
2014-01-16
Total views
5 ( #1,208,349 of 2,520,891 )
Recent downloads (6 months)
1 ( #405,457 of 2,520,891 )
2014-01-16
Total views
5 ( #1,208,349 of 2,520,891 )
Recent downloads (6 months)
1 ( #405,457 of 2,520,891 )
How can I increase my downloads?
Downloads