Showing cs.CCShow all
2 papers · 1 filter
cs.CC2025
The Structure of In-Place Space-Bounded Computation
James Cook, Surendra Ghentiyala, Ian Mertz +2
In the standard model of computing multi-output functions in logspace (), we are given a read-only tape holding and a logarithmic length worktape, and must print $…
cs.CC2025
Collapsing Catalytic Classes
Michal Koucký, Ian Mertz, Edward Pyne +1
A catalytic machine is a space-bounded Turing machine with additional access to a second, much larger work tape, with the caveat that this tape is full, and its contents must be pr…