Memoization of Amortized Constant Time and Constant Garbage Usage for Reversible Programs

Tetsuo YOKOYAMA  

Publication
D - Abstracts of IEICE TRANSACTIONS on Information and Systems (Japanese Edition)   Vol.J100-D   No.10   pp.895-896
Publication Date: 2017/10/01
Online ISSN: 1881-0225
Type of Manuscript: LETTER
Category: 
Keyword: 
reversible program,  memoization,  abstract interpretation,  Janus,  

Full Text(in Japanese): PDF(168.2KB)
>>Buy this Article


Summary: 
We propose a reversible version of memoized recursive algorithms. The resulting reversible program is the abstract interpretation of reversible binary counters. We show that given any sequence represented by injective recurrence relations there is a reversible program of constant amortized time and constant garbage usage.