Partially Reversible Algorithms

The DC will study the trade-off between lost information, time complexity and space complexity in reversible algorithms. The work will build on the framework and technique used in the literature to study many specific algorithms and data structures. First, the framework will be implemented and further algorithms and data structures will be considered, e.g., hashing, dynamic programming and geometric algorithms. Then the DC will look for general methodologies and theories to understand the trade-off for given algorithms as well as finding concrete solutions given the desired preferences. Specific algorithms of interest, possibly suggested by WP4 DCs, will be considered to exercise the framework and test its effectiveness. The DC will interact with WP 1 and WP 3 DCs to study the support needed at language and architecture level to enable the execution of partially reversible algorithms.

1) An implementation of a framework in the literature to enable experimentation; 2) Analysis of lost information/time/space trade-offs for algorithms of interest; 3) A theory and methodology to study the trade-offs in 1).

M14, UCPH, R. Glück, extended notation for partially reversible algorithms; M33, AGH, I. Ulidowski, reversible and partially-reversible algorithms; M36, UoM, M. Lujan, architectural support for partially reversible algorithms.