A machine description and the hierarchy of initial Grzegorczyk classes
From MaRDI portal
Publication:1168308
DOI10.1007/BF01629435zbMath0493.03012MaRDI QIDQ1168308
Publication date: 1982
Published in: Journal of Soviet Mathematics (Search for Journal in Brave)
complexity classes; Grzegorczyk hierarchy; control device; Smullyan's rudimentary predicate class; stack register machines
03D15: Complexity of computation (including implicit computational complexity)
03D20: Recursive functions and relations, subrecursive hierarchies
03D10: Turing machines and related notions
Related Items
Computation models and function algebras, Regressive computations characterize logarithmic space, Register machines with counters, Deterministic summation modulo \(\mathcal B_{n}\), the semigroup of binary relations on \(0,1, \dots, n-1\), Computations on register machines with counters, Nonerasing, counting, and majority over the linear time hierarchy, Arithmetization of register machines with counters
Cites Work