Showing cs.LOShow all
2 papers · 1 filter
cs.LO2026
Step Recursion: Exact Depth Does Not Determine Algebraic Expressiveness
Kirill Osipov
Step recursion is a form of bounded recursion in which each recursive call moves from an input y to a prescribed predecessor . Its depth is the exact number of suc…
cs.LO2026
Step Recursion: A Three-Parameter Refinement of the Grzegorczyk Hierarchy
Kirill Osipov
We ask whether asymptotic recursion depth determines the expressive strength of a bounded recursive algebra, and prove that it does not. We replace ordinary predecessor recursion b…