WG211/M21Glueck - Revision history

Robert at 09:59, 10 August 2022

2022-08-10T09:59:27Z

← Older revision		Revision as of 11:59, 10 August 2022
Line 1:		Line 1:
	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 ~~reversibly~~ recurrence functions. The costs compare favorably to classic memoization: bounded space and amortized linear running time. Joint work with Tetsuo Yokoyama.		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.

Robert at 09:58, 10 August 2022

2022-08-10T09:58:54Z

← Older revision		Revision as of 11:58, 10 August 2022
Line 1:		Line 1:
	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 ~~the~~ 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 reversibly recurrence functions. The costs compare favorably to classic memoization: bounded space and amortized linear running time. Joint work with Tetsuo Yokoyama.		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 reversibly recurrence functions. The costs compare favorably to classic memoization: bounded space and amortized linear running time. Joint work with Tetsuo Yokoyama.

Robert at 09:58, 10 August 2022

2022-08-10T09:58:28Z

← Older revision		Revision as of 11:58, 10 August 2022
Line 1:		Line 1:
	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.		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 the 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 reversibly recurrence functions. The costs compare favorably to classic memoization: bounded space and amortized linear running time. Joint work with Tetsuo Yokoyama.

Robert: Created page with "The design and implementation of efficient algorithms for reversible computing systems requires an unconventional way of thinking. Memoization is a classic program optimizatio..."

2022-08-10T09:56:06Z

Created page with "The design and implementation of efficient algorithms for reversible computing systems requires an unconventional way of thinking. Memoization is a classic program optimizatio..."

New page

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.