Reversible Sequential General-Purpose Algorithms

This DC will develop reversible versions of algorithms for standard computation tasks, and deliver reversible versions of fundamental data structures and reversible operations on them. The DC will provide a notation for writing reversible algorithms taking inspiration from the reversible language Janus. The DC will then define methods for converting a traditional algorithm into its reversible version written in our notation, and then into the inverse algorithm that un-computes the result of the original algorithm. These methods will be applied in the areas of lossless compression and decompression of data, where the DC will analyse energy-efficiency as well as space and time complexity. Additionally, the DC will collaborate with DC2 and DC5 and provide support to WP 4 studentships.

1) Notation for reversible algorithms and data structures; 2) Method for converting standard algorithms into reversible versions, and for producing inverted versions of reversible algorithms; 3) Analysis of energy-efficiency, space and time complexity of reversible algorithms; 4) Application to lossless compression and decompression algorithms, and to algorithms from WP 4.

M14, UCPH, R. Glück, Reversible data structures, notation for reversible algorithms; M20, UNIBO, I. Lanese, Converting standard algorithms to their reversible versions; M32, ULEIC, J. Hoey, Analysis of energy-efficiency, space and time complexity of reversible algorithms.