Strong enumeration reducibilities

DOI10.1007/S00153-006-0012-4MaRDI QIDQ850805zbMATH OpenOpenAlexFDO

Authors Andrea Sorbi, Roland Sh. Omanadze

Publication date 6 November 2006

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00153-006-0012-4

zbMATH Keywords

\(s\)-reducibility\(e\)-reducibility

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• Strong Positive Reducibilities
• Embeddings in the Strong Reducibilities Between 1 and npm
• On distributivity of the upper semilattices of the degrees below 0'
• Bounded enumeration reducibility and its degree structure
• On the symmetric enumeration degrees

Cites work

• 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?)
• 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
• Embedding the diamond in the Σ₂ enumeration degrees
• Enumeration Reducibility Using Bounded Information: Counting Minimal Covers
• Enumeration reducibilities
• Enumeration reducibility and partial degrees
• Jumps of quasi-minimal enumeration degrees
• Noncappable enumeration degrees below 0_e^′
• 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 Σ₂ 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
• e- and s-degrees

Cited in

(21)

• Lattice embeddings for abstract bounded reducibilities
• On the bounded quasi‐degrees of c.e. sets
• Incomparability in local structures of \(s\)-degrees and \(Q\)-degrees
• Barendregt's problem \#26 and combinatory strong reduction
• The structure of the s-degrees contained within a single e-degree
• New Computational Paradigms
• Strong Positive Reducibilities
• Embeddings into the Medvedev and Muchnik lattices of \(\Pi^0_1\) classes
• Embedding finite lattices into the Σ₂⁰ enumeration degrees
• s-Degrees within e-Degrees
• Goodness in the enumeration and singleton degrees
• Strong Reducibilities of Enumerations and Partial Enumerated Algebras
• A characterization of the δ₂⁰ hyperhyperimmune sets
• \(sQ_1\)-degrees of computably enumerable sets
• Counting on strong composition as identity to settle the special composition question
• Bounded enumeration reducibility and its degree structure
• Strong combinatorial principles and level by level equivalence
• Enumeration of strong dichotomy patterns
• r‐Maximal sets and Q1,N‐reducibility
• \(Q _{1}\)-degrees of c.e. sets
• On the symmetric enumeration 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)