On the density of honest subrecursive classes
From MaRDI portal
Publication:1229713
DOI10.1016/S0022-0000(75)80039-0zbMath0336.02031MaRDI QIDQ1229713
Publication date: 1975
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Recursive functions and relations, subrecursive hierarchies (03D20)
Related Items
Reductions among polynomial isomorphism types, The structure of the honest polynomial m-degrees, Indexings of subrecursive classes, Streamlined subrecursive degree theory, Semi-honest subrecursive degrees and the collection rule in arithmetic, A maximal sequence of classes transformable by primitive recursion in a given class, Honest elementary degrees and degrees of relative provability without the cupping property, Augmented loop languages and classes of computable functions, Polynomial and abstract subrecursive classes, Subrekursive Komplexität bei Gruppen. II: Der Einbettungssatz von Higman für entscheidbare Gruppen, Cook reducibility is faster than Karp reducibility in NP, Finite complete rewriting systems and the complexity of word problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Augmented loop languages and classes of computable functions
- On a Subrecursive Hierarchy and Primitive Recursive Degrees
- Gödel numberings of partial recursive functions
- Classes of Predictably Computable Functions
- The honest subrecursive classes are a lattice
- A Machine-Independent Theory of the Complexity of Recursive Functions
- A Classification of the Recursive Functions