WG211/M21Glueck

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