For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Memoization of Amortized Constant Time and Constant Garbage Usage for Reversible Programs
D - Abstracts of IEICE TRANSACTIONS on Information and Systems (Japanese Edition)
Publication Date: 2017/10/01
Online ISSN: 1881-0225
Type of Manuscript: LETTER
reversible program, memoization, abstract interpretation, Janus,
Full Text(in Japanese): PDF(168.2KB)
>>Buy this Article
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.