非明示的表現に対するアルゴリズムの開発

点击翻译按钮获取中文摘要

本研究は,非明示的に表現されたオブジェクトに対するアルゴリズムの開発とその計算量の解析を行うことを目的し,また同時に,効率のよいアルゴリズムの開発に適した非明示的な表現法を文字列やグラフなどの離散構造を対象として研究を展開してきた.具体的には,直線的プログラムとして圧縮表現された文字列を対象として,繰り返し構造や共通部分を検出する問題に取り組んだ.直線的プログラムは,文字列の連結を基本命令とした代入式の列であり,種々の文法圧縮,辞書式圧縮を抽象化したものである.もしもこの直線的プログラムからもとの文字列を陽に展開してしまうと,その長さは指数的に長くなりうるため,決して多項式時間で処理を行うことができない.我々は文字列に内在する組み合わせ構造や周期に着目することにより,圧縮文字列に含まれる回文構造の検出や,最大共通部分文字列の計算を多項式時間で行うアルゴリズムを開発した.また,漸化式として表される文字列の性質を調べた.隣接2項の漸化式で表されるフィボナッチ文字列を一般化し,隣接n項の漸化式でn-ボナッチ文字列を定義した.本研究では,任意のn≧2に対して,無限n-ボナッチ文字列における第k項目の有限n-ボナッチ文字列の最大連続出現数はk→∞のとき2+1/(φ(n)-1)に収束することを証明した.ここに,φ(n)はn-ボナッチ定数であり,特にφ(2)=(1+√<5>)/2は黄金比として知られている.さらに,nを増加させると,最大連続数はちょうど3に近づくことを示した.