Data representation and computational complexity

DOI10.1016/0304-3975(78)90042-7zbMath0421.03029OpenAlexW2060982502MaRDI QIDQ1132872

Rutger Verbeek, Weihrauch, Klaus

Publication date: 1978

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(78)90042-7

zbMATH Keywords

numberingsdata representationGödelizationsstrong hierarchy theorem for bijections

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Data structures (68P05) Theory of numerations, effectively presented structures (03D45) Theory of computing (68Q99) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Cites Work

• On the computational power of pushdown automata
• Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
• Rekursive Wortfunktionen
• Über die Verallgemeinerung der Theorie der Rekursiven Funktionen für Abstrakte Mengen Geeigneter Struktur als Definitionsbereiche
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Primitiv-Rekursive Funktionen Über Einem Bereich Endlicher Mengen
• A Classification of the Recursive Functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item