再帰データ上の最適化問題の解法およびその応用に関する研究

最大マーク付け問題に対する一般的解法はすでに与えたが、実現する際には個々の問題のデータ型に対して別々に最適化関数を記述する必要があった。Haskell等の通常の関数型言語でも擬似的に一般的関数を記述できるが、データ型に応じてプログラムを変更しなければならなかった(R.Bird, JFP 11(4),2001)。現在開発が行われているGeneric Haskellという一般的プログラミングのための言語を用いることにより、データ型に依存しない最適化関数を記述した(WRSC2003で発表)。最大マーク付け問題は多くの実際的応用例を持っており、その一例として、データマイニングにおけるあるクラスの最適区間問題に対する線形時間アルゴリズムの単純な仕様からの導出法を与え、結果として既存のアルゴリズムと効率は同等であるが新たなアルゴリズムを得た(コンピュータソフトウェア第19巻第4号)。また、他の実際的な例として、プログラム解析に対する応用の可能性を探った。第一歩としてdead code検出を最大マーク付け問題で定式化し、単純な仕様から、goto文のないC言語プログラム等の構造的プログラムに対するdead code検出を行う線形時間アルゴリズムを機械的に得る手法を与えた(ESOP2003に投稿)。他のプログラム解析の例として、Generalized dominator問題の構造的プログラムに対する線形時間アルゴリズムの導出を試みた。この問題に対しては制限のないグラフ上でのO(|V||E|)のアルゴリズム、またtree widthが有界のグラフクラスに対する線形時間アルゴリズムがすでに知られている。O(|V||E|)のアルゴリズムは深さ優先探索をO(|V|)回行うという非常に単純なものであるが、tree widthが有界のクラスに対する線形アルゴリズムは非常に複雑である。この2つのアルゴリズムが変換によって関連付けられると興味深い。

最大マーク付け問題に対する一般的解法はすでに与えたが、実現する際には個々の問題のデータ型に対して別々に最適化関数を記述する必要があった。Haskell等の通常の関数型言語でも擬似的に一般的関数を記述できるが、データ型に応じてプログラムを変更しなければならなかった(R.Bird, JFP 11(4),2001)。現在開発が行われているGeneric Haskellという一般的プログラミングのための言語を用いることにより、データ型に依存しない最適化関数を記述した(WRSC2003で発表)。最大マーク付け問題は多くの実際的応用例を持っており、その一例として、データマイニングにおけるあるクラスの最適区間問題に対する線形時間アルゴリズムの単純な仕様からの導出法を与え、結果として既存のアルゴリズムと効率は同等であるが新たなアルゴリズムを得た(コンピュータソフトウェア第19巻第4号)。また、他の実際的な例として、プログラム解析に対する応用の可能性を探った。第一歩としてdead code検出を最大マーク付け問題で定式化し、単純な仕様から、goto文のないC言語プログラム等の構造的プログラムに対するdead code検出を行う線形時間アルゴリズムを機械的に得る手法を与えた(ESOP2003に投稿)。他のプログラム解析の例として、Generalized dominator問題の構造的プログラムに対する線形時間アルゴリズムの導出を試みた。この問題に対しては制限のないグラフ上でのO(|V||E|)のアルゴリズム、またtree widthが有界のグラフクラスに対する線形時間アルゴリズムがすでに知られている。O(|V||E|)のアルゴリズムは深さ優先探索をO(|V|)回行うという非常に単純なものであるが、tree widthが有界のクラスに対する線形アルゴリズムは非常に複雑である。この2つのアルゴリズムが変換によって関連付けられると興味深い。