2 papers
cs.CC2026
Understanding Robust Catalytic Computing
Michal Koucký, Ian Mertz, Sasha Sami
Catalytic computing concerns space bounded computation which starts with memory full of data that have to be restored by the end of the computation. Lossy catalytic computing, defi…
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…