連想メモリを利用した高速単一化アルゴリズム

概要

論文の詳細を見る
単一化(unification)は、与えられた2つの項のMGU(Most General Unifier)を求める操作で、Prolog等の論理型言語の基本操作として重要な演算の一つである。単一化は、項を項グラフによって表すことにより、項グラフ上の節点の同値分割と見なすことができ、UNIONとFINDという集合に対する2つの操作によって処理することができる。これらの操作は、単一化の他、minimum spanning treeを求める問題や、決定性有限オートマトンの等価性判定、switching level simulation等、幅広い応用が考えられる。しかし、UNION-FIND問題をソフトウェアによって効率良く処理するためには、複雑なデータ構造と、それに対する操作を必要とする。本稿では、UNION-FIND問題を高速に処理するために、連想メモリ(CAM)を利用する方法を提案し、また、この方法を単一化に応用した際の処理時間について考察する。
社団法人情報処理学会の論文
1986-10-01