可逆プログラムのための償却定数時間かつ定数ゴミ使用量のメモ化

横山 哲郎  

誌名
電子情報通信学会論文誌 D   Vol.J100-D   No.10   pp.895-896
発行日: 2017/10/01
Online ISSN: 1881-0225
論文種別: レター
専門分野: 
キーワード: 
可逆プログラム,  メモ化,  抽象解釈,  Janus,  

本文: PDF(168.2KB)
>>論文を購入


あらまし: 
メモ化アルゴリズムの可逆版を提案する.本手法により得られるクリーン可逆プログラムは,可逆二進計数器を抽象解釈とする.単射な隣接2項間漸化式で表される任意の数列に対して償却定数時間で定数ゴミ使用量の可逆プログラムを得る方法を示す.