Arithmetization of register machines with counters

DOI10.3103/S0278641920030048zbMath1477.03160OpenAlexW3084778673MaRDI QIDQ2212730

Igor V. Savitskiy

Publication date: 24 November 2020

Published in: Moscow University Computational Mathematics and Cybernetics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3103/s0278641920030048

zbMATH Keywords

Grzegorczyk classesregister machines with countersbasis according to superpositioning

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A machine description and the hierarchy of initial Grzegorczyk classes
• Nondeterministic stack register machines
• Computations on register machines with counters
• Computations on counter machines with summator
• Eliminating inequalities in register machines with counters
• Generating some classes of recursive functions by superpositions of simple arithmetic functions
• Bases for AC0 and Other Complexity Classes
• CRN Elimination and Substitution Bases for Complexity Classes
• An example of a simple quasi-universal function in the class ε 2 of the Grzegorczyk hierarchy

This page was built for publication: Arithmetization of register machines with counters