On the computational power of automata with time or space bounded by Ackermann's or superexponential functions

DOI10.1016/0304-3975(81)90072-4zbMath0475.03018OpenAlexW1990157773MaRDI QIDQ1159662

Ren-ji Tao

Publication date: 1981

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

Full work available at URL: https://doi.org/10.1016/0304-3975(81)90072-4

zbMATH Keywords

partial functionscomplexity classesAckermann's functiontotal functionsGrzegorczyk hierarchy

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On primitive recursive wordfunctions
• Classes of recursive functions based on Ackermann's function
• Classes of Predictably Computable Functions
• Rekursionszahlen und die Grzegorczyk-Hierarchie
• A Classification of the Recursive Functions
• Computability of Recursive Functions