正規言語間の順序同型写像の応用

正規言語間の順序同型写像の性質を探るために、順序同型写像によって極端に圧縮される言語の属について考察を行った。まず言語に対する自然な”測度”(大きさ)を定式化し、測度が0になる正規言語の代数的・オートマトン的な必要十分条件を与えた。測度が0になる正規言語は、本研究課題で提案している順序同型写像による圧縮手法によって極端に圧縮される。具体的には，次の結果を得た．（１）正規言語の測度が0になることの代数的・オートマトン的必要十分条件を与えた。また、オートマトン的な特徴付けから、「与えられたDFAの受理する言語の測度が0になるか」の判定がDFAの状態数に対して線形時間で決定するアルゴリズムを構成した。これらの成果は H26年度からの研究テーマである「閉包性の高い正規言語のクラスの考察」の延長線上にあり、証明技法はVariety Theoryと呼ばれる正規言語の理論フレームワークに則っている。（2）与えられた言語が正規言語であることの必要条件を求めた。この必要条件は(1)の成果から従うものである。得られた十分条件は言語の測度に基づくものであり、正規言語に対する既存の十分条件であるMyhill-Nerodeの定理やポンピング補題とは全く異なる条件となっている。

正規言語間の順序同型写像の性質を探るために、順序同型写像によって極端に圧縮される言語の属について考察を行った。まず言語に対する自然な”測度”(大きさ)を定式化し、測度が0になる正規言語の代数的・オートマトン的な必要十分条件を与えた。測度が0になる正規言語は、本研究課題で提案している順序同型写像による圧縮手法によって極端に圧縮される。具体的には，次の結果を得た．（１）正規言語の測度が0になることの代数的・オートマトン的必要十分条件を与えた。また、オートマトン的な特徴付けから、「与えられたDFAの受理する言語の測度が0になるか」の判定がDFAの状態数に対して線形時間で決定するアルゴリズムを構成した。これらの成果は H26年度からの研究テーマである「閉包性の高い正規言語のクラスの考察」の延長線上にあり、証明技法はVariety Theoryと呼ばれる正規言語の理論フレームワークに則っている。（2）与えられた言語が正規言語であることの必要条件を求めた。この必要条件は(1)の成果から従うものである。得られた十分条件は言語の測度に基づくものであり、正規言語に対する既存の十分条件であるMyhill-Nerodeの定理やポンピング補題とは全く異なる条件となっている。