Strong enumeration reducibilities
This paper discusses various enumeration reducibilities, with primary emphasis on \(s\)-reducibility. Let \(L\) denote the structure of \(s\)-degrees below \({\mathbf 0}'_s\) (equivalently, the \(\Sigma_2^0\) \(s\)-degrees). The authors prove that a countable atomless Boolean algebra (and hence any countable distributive lattice) is embeddable in \(L\). On the other hand, they show that \(L\) itself is not distributive by embedding the nondistributive lattice \(N_5\) in it. The authors also prove that \(L\) is upwards dense -- indeed, for any \(s\)-degree \({\mathbf a}<{\mathbf 0}'_s\), every countable partial order is embeddable between \({\mathbf a}\) and \({\mathbf 0}'_s\).
- A class of hypersimple incomplete sets
- Bounding and nonbounding minimal pairs in the enumeration degrees
- Classical recursion theory. The theory of functions and sets of natural numbers
- Classical recursion theory. Vol. II
- Computably enumerable sets and quasi-reducibility
- Computational complexity, speedable and levelable sets
- Cupping and noncapping in the r.e. weak truth table and turing degrees
- e- and s-degrees
- Embedding the diamond in the Σ2 enumeration degrees
- Enumeration reducibilities
- Enumeration reducibility and partial degrees
- Enumeration Reducibility Using Bounded Information: Counting Minimal Covers
- scientific article; zbMATH DE number 1048046 (Why is no real title available?)
- scientific article; zbMATH DE number 2039009 (Why is no real title available?)
- scientific article; zbMATH DE number 3999903 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- Jumps of quasi-minimal enumeration degrees
- Noncappable enumeration degrees below 0e′
- On minimal pairs of enumeration degrees
- On restricted forms of enumeration reducibility
- On subcreative sets and S-reducibility
- On the degrees less than 0'
- Partial degrees and the density problem
- Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ2 sets are dense
- Reducibility and Completeness for Sets of Integers
- Semirecursive Sets and Positive Reducibility
- The \(n\)-rea enumeration degrees are dense
- Upper semilattice of recursively enumerable sQ-degrees
- The structure of the s-degrees contained within a single e-degree
- Counting on strong composition as identity to settle the special composition question
- Barendregt's problem \#26 and combinatory strong reduction
- Incomparability in local structures of \(s\)-degrees and \(Q\)-degrees
- On the symmetric enumeration degrees
- sQ₁-degrees of computably enumerable sets
- Strong combinatorial principles and level by level equivalence
- Lattice embeddings for abstract bounded reducibilities
- s-Degrees within e-Degrees
- Strong Positive Reducibilities
- Strong Reducibilities of Enumerations and Partial Enumerated Algebras
- Embeddings in the Strong Reducibilities Between 1 and npm
- \(Q _{1}\)-degrees of c.e. sets
- Embedding finite lattices into the Σ20 enumeration degrees
- Enumeration of strong dichotomy patterns
- On the bounded quasi‐degrees of c.e. sets
- A characterization of the δ20 hyperhyperimmune sets
- New Computational Paradigms
- r‐Maximal sets and Q1,N‐reducibility
- Bounded enumeration reducibility and its degree structure
- On minimal pairs of quasi-degrees
- Non-empty open intervals of computably enumerable sQ₁-degrees
- The singleton degrees of the \({\Sigma}_2^0\) sets are not dense
- Embeddings into the Medvedev and Muchnik lattices of ^0_1 classes
- Goodness in the enumeration and singleton degrees
This page was built for publication: Strong enumeration reducibilities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q850805)
