著者

新屋 良磨 山口 勇太郎 中村 誠希

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.40, no.2, pp.2_49-2_60, 2023-04-21 (Released:2023-06-21)

---

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