苫米地英人
準破壊型グラフ・ユニフィケーション
Abstract:単一化文法を使う解析法において、グラフ単一化の操作が最も計算コストを要する。この操作
を高速に処理する実現手法について報告する。次の2点に関する改良を図り、単一化アルゴリ
ズムの高速化を実現した。それらは、成功時だけ単一化操作によるグラフの複製を作ること、
および単一化失敗を早期に発見すること、の2点である。解析実験により、代表的な単一化ア
ルゴリズムの一つであるWroblewskiのものと比べ、同等乃至は2倍の高速化が確認できた。