Upper semilattice of recursively enumerable sQ-degrees
From MaRDI portal
Publication:1803017
DOI10.1007/BF01985061zbMath0788.03060MaRDI QIDQ1803017
Publication date: 29 June 1993
Published in: Algebra and Logic (Search for Journal in Brave)
density; speedability; \(sQ\)-reducibility; abstract complexity properties; upper semilattice of recursively enumerable \(sQ\)- degrees
03D15: Complexity of computation (including implicit computational complexity)
03D25: Recursively (computably) enumerable sets and degrees
03D30: Other degrees and reducibilities in computability and recursion theory
Related Items
r‐Maximal sets and Q1,N‐reducibility, \(Q _{1}\)-degrees of c.e. sets, Immunity properties and strong positive reducibilities, Strong enumeration reducibilities, \(sQ_1\)-degrees of computably enumerable sets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Upper semilattice of recursively enumerable Q-degrees
- Three theorems on the degrees of recursively enumerable sets
- On the Cartesian subalgebras of a free Lie sum of Lie algebras
- Effectively nowhere simple sets
- On complexity properties of recursively enumerable sets
- Nowhere simple sets and the lattice of recursively enumerable sets
- Computational complexity, speedable and levelable sets