WG211/M21Glueck

The design and implementation of efficient algorithms for reversible computing systems requires an unconventional way of thinking. Memoization is a classic program optimization technique that stores the result of a computation in memory. Unfortunately, it is not immediately clear how memoization can be made reversible without adding unbounded tracing. This work-in-progress presention discusses a surprising solution using cyclic state transition systems to reversibly memoize recurrence functions. The costs compare favorably to conventional memoization: bounded space and amortized linear running time. Joint work with Tetsuo Yokoyama.