拡張正規表現所属問題および検索問題に対するDFA型アルゴリズムの効率的な実装について

概要

論文の詳細を見る
正規表現はコンピュータサイエンスの分野で広く利用されている。本論文では、正規表現に共通集合演算および補集合演算を加えた拡張正規表現(EREと略す)の所属問題および検索問題を扱う。所属問題は、アルファベットΣ上のEREr及び記号列xが与えられたとき、x∈L(r)かどうかを判定する問題である。また、検索問題は、xからy∈L(r)なるすべての部分列yを見つけ出す問題である。ここで、L(r)はL(r)によって表される言語を意味する。そのとき、我々はO(n^2(k_12^H+(k-k_1)⌈n/log n⌉)時間かつO(n(k_12^H+(k-k_1)⌈n/log n⌉)領域で所属問題を解くアルゴリズムを与える。さらに、このアルゴリズムを拡張して、同程度の計算量で検索問題を解くことができることも示す。ここで、nはxの長さ、kはrに出現する共通集合演算及び補集合演算(これらを拡張演算子と呼ぶ)の数を表し、その内k_1は、我々が良性と呼ぶある条件を満たす拡張演算子の数である。また、HはH=max{m_j|m_jはrのj番目のモジュールに出現するΣの記号と拡張演算子の数}と定義する。
社団法人電子情報通信学会の論文
2007-06-22