A Study on Efficient Program Reversibilization with Minimum Extra Data

本研究の主目的はゴミ出力量を最適化した可逆化の方法を構築し特定の問題領域における可逆化への系統的な適用をすることである。任意の単射部分関数に対するゴミ出力がない可逆化は知られていたが、任意の部分関数に対するゴミ出力がある場合の(1)最適な一般解法や(2)特定の問題領域への系統的な適用は知られていなかった。本年度はこの両者に一定の成果が得られた。(1)重要な問題のひとつは、余剰出力が最小限な可逆プログラムが存在するかである。可算領域上の部分関数を実装するプログラムについてこの問いに答えるため、我々は、無限ゴミ集合に関する順序及び最小性の概念を導入した。我々は、決定可能及び半決定可能な述語で指定された関数のための2つの方法を提示した。両手法は普遍的であり、述語で指定された全てのプログラムに対して適用可能である。これらの方法は、Bennettの古典的な単射関数の入力消去可逆模倣を包含するものである。したがって、チューリング完全なプログラミング言語で書かれたプログラムは、rチューリング完全な可逆言語において、g最小性ゴミをもつものとして実装することができる。ただし、こうした一般化のために生成とテストのアプローチを用いており、相当の実行時間を犠牲にしていることには注意されたい。(2)文字列照合はアルゴリズムの基本問題である。本年度では、2つの可逆的な文字列照合アルゴリズムを検討した。我々は、基本的な可逆プログラミング技法を用いて、Rabin-Karpアルゴリズムが採用する多項式ハッシュ更新関数の効率的な可逆化を実現した。その結果得られた2つのクリーンな入力保存型可逆アルゴリズムは、追加のメモリ使用量を必要とせず、古典的な非可逆的な元のアルゴリズムと同じ漸近的時間複雑性を持つようになった。この問題の探究を通じて可逆アルゴリズム及び可逆プログラミングの理論の整備に寄与することができた。

本研究の主目的はゴミ出力量を最適化した可逆化の方法を構築し特定の問題領域における可逆化への系統的な適用をすることである。任意の単射部分関数に対するゴミ出力がない可逆化は知られていたが、任意の部分関数に対するゴミ出力がある場合の(1)最適な一般解法や(2)特定の問題領域への系統的な適用は知られていなかった。本年度はこの両者に一定の成果が得られた。(1)重要な問題のひとつは、余剰出力が最小限な可逆プログラムが存在するかである。可算領域上の部分関数を実装するプログラムについてこの問いに答えるため、我々は、無限ゴミ集合に関する順序及び最小性の概念を導入した。我々は、決定可能及び半決定可能な述語で指定された関数のための2つの方法を提示した。両手法は普遍的であり、述語で指定された全てのプログラムに対して適用可能である。これらの方法は、Bennettの古典的な単射関数の入力消去可逆模倣を包含するものである。したがって、チューリング完全なプログラミング言語で書かれたプログラムは、rチューリング完全な可逆言語において、g最小性ゴミをもつものとして実装することができる。ただし、こうした一般化のために生成とテストのアプローチを用いており、相当の実行時間を犠牲にしていることには注意されたい。(2)文字列照合はアルゴリズムの基本問題である。本年度では、2つの可逆的な文字列照合アルゴリズムを検討した。我々は、基本的な可逆プログラミング技法を用いて、Rabin-Karpアルゴリズムが採用する多項式ハッシュ更新関数の効率的な可逆化を実現した。その結果得られた2つのクリーンな入力保存型可逆アルゴリズムは、追加のメモリ使用量を必要とせず、古典的な非可逆的な元のアルゴリズムと同じ漸近的時間複雑性を持つようになった。この問題の探究を通じて可逆アルゴリズム及び可逆プログラミングの理論の整備に寄与することができた。