結合則と交換則を伴う unification 問題の計算複雑さ
On the parameterized complexity of associative and commutative unification

概要

本研究では結合則(A)、交換則(C)、結合-交換則(AC)を伴う関数の
unification 問題に対し、変数の数に関する parameterized complexity を解析する。
もし各変数が1回ずつしか現れなければ、A-unification と AC-unification は
多項式時間で解けることが示される。しかし一般的には、2つの入力項のうち1つが
変数を含まない場合ですら W[1]-hard である。
C-unification に関しては、変数の数の指数時間アルゴリズムを示すが、
ある予想が正しい場合には、1つの入力項に変数が含まれない特別な場合は
FPTに含まれる。
また変数を許す文字列や木の編集距離問題に対するいくつかの関連結果も示す。

産業界への展開例・適用分野

数式検索、変数を含む同一性判定

研究者

氏名	専攻	研究室	役職/学年
田村 武幸	知能情報学専攻	数理生物情報	助教

---