抄録
A-004
ファクターオラクルの拡張と実験的評価
◎大井恒平・山本博章・藤原洋志(信州大)
文字列に対するファクターオラクルとは、少なくとその文字列のすべての
部分文字列を認識するDFAである。すなわち、部分文字列でない文字列
を受理する場合がある。
本論文では、まず、ファクターオラクルの新たな構成法を示し、
それが従来のファクターオラクルと同一になることを示す。提案法は、
NFAをDFAに変換する構成法に基づいており、拡張性が高い。
我々は、提案法に基づいて、ファクターオラクルを文字列から複数文字列に
対応するオートマトンへと拡張する。