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

DOI10.1016/0304-3975(81)90072-4zbMath0475.03018MaRDI 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 functions; complexity classes; Ackermann's function; total functions; Grzegorczyk hierarchy

Mathematics Subject Classification ID

03D05: Automata and formal grammars in connection with logical questions

03D15: Complexity of computation (including implicit computational complexity)

03D20: Recursive functions and relations, subrecursive hierarchies

03D10: Turing machines and related notions

03D60: Computability and recursion theory on ordinals, admissible sets, etc.

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item