6J-08
グラフ書換え系言語LMNtalにおけるパターンマッチングの実行時最適化
○柳川峻広，上田和紀（早大）
LMNtalとはグラフと書換えルールからなるグラフ書換え言語である.書換えルールはグラフ構造,比較演算,型制約などによる制約条件が合う部分グラフに対して適用される.
LMNtalの実行時処理系SLIMは,LMNtalコンパイラが出力する中間命令列を解釈実行する.そのため,書換えルール適用時の部分グラフを探索する命令列は静的に決まる.
本研究では,書換えルールの制約を満たす部分グラフを動的に探索することで,グラフの規模が大きい問題に対して最適化を図る.具体的には,ルールにマッチするグラフを絞り込み,探索におけるバックトラックの回数が少なくなるような順序でグラフを探索する.
footer 著作権について 倫理綱領 プライバシーポリシー セキュリティ 情報処理学会