4 papers
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…
Step Recursion: Mixed Stride Spectra, Path Factorization, and Synchronization Geometry
Kirill Osipov
Step recursion allows recursive computation to move through a canonical hierarchy in jumps, or strides. Suppose a function algebra is allowed to use several primitive stride length…
Step Recursion: Resource Profiles and Descent Quotients
Kirill Osipov
We develop a resource representation for step recursion in which mutable-state width and recursion descent are explicit and independent parameters. A width bound controls the s…
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…