部分語の出現情報の検査のみで近似できる正規言語について

摘要

言語Lが正規可測であるとは,Lに「収束」する正規言語の対の無限列が存在することを言う.本論文では,正規言語の代わりに正規言語の部分クラスである区分検査可能(Piecewise Testable(PT):部分語の出現情報のBool演算で記述可能)言語および文字検査可能(Alphabet Testable(AT):文字の出現情報のBool演算で記述可能)言語に焦点を当てその可測性を考察する.特に,正規言語に対するAT可測性はco-NP完全である一方,PT可測性は線形時間で決定できることを示す.