Title Transcriptionイロツキ ジュリ ジョウタイ オ モツ オートマタ ト ソレラ ノ ヒコンショク セイ モンダイ ニ カンスル ケンキュウ
Alternative TitleA study on automata with colored accepting states and their unmixedness problems
Note (General)オートマトン理論と形式言語理論のいくつかの文献では，2進ｎ次元ドブリュイングラフと，正規言語(0+1)*1(0+1)^{n-1}を受理する最小状態数の決定性有限オートマトンD2,nの状態遷移図が同型であることを暗に示している．この2進の場合の同型性は比較的容易に証明されるが，この結果をk進に拡張した場合の同型性を厳密に証明することが望まれる．本研究ではこの第1の目的を達成するために，新たに“色付き有限オートマトン(CFA) "という計算モデルを導入し，正規言語によって一般のk進ドブリュイングラフに対するある種の特徴づけを与える．本研究の第2の目的は，受理状態を多色化することにより入力文字列を多種類に類別可能にしたこのオートマトンの性質を更に考察することにある．ところで，CFAが非決定性(NCFA)の場合には，的確な識別を可能にする為には受理状態の色が混色していない（すなわち，異なる2色以上の受理状態で受理されるような入力が存在しない）状況が望まれる．そこで，非混色性に関する計算量理論上の三つの決定問題（非混色性検証問題，非混色分割問題，非混色拡張問題）を新たに提案し，それぞれの計算複雑さがNLOG完全,P,ならびにNP完全であることを明らかにする．なお，色付き有限オートマトンの正規表現エンジンやモデル検査への応用も例示する．次に，色付き受理の概念をプッシュダウン・オートマトンに適用した‘‘色付きプッシユダウン・オートマトン( CPDA) "を新たに導入し，上述の非混色性判定問題すべてが決定不能となる一方，対象を非曖昧なオートマトンに限定すると一部の問題が常に真な問題に容易化することを示す．このように，色付き受理の概念は受理状態集合を持つような任意のオートマトンモデルに適用可能であり，その理論上ならびに応用上の幅広い有用性が今後期待される．
Some textbooks of formal languages and automata theory implicitly state the structural equality of the binary n-dimensional de Bruijn graph and the state diagram of minimum state deterministic finite automaton which accepts regular language (0+1)*1(0+1)^{n-1}. Although the isomorphism in binary case is relatively easy to prove, it is desirable to rigorously prove such an isomorphism in general k-ary case. To achieve this purpose, the author introduces a new computational model, called "colored finite automata (CFA)," and give a certain characterization of the general k-ary de Bruijn graphs by regular languages.The second purpose of this study is to investigate the potential of this automaton with multi-colored accepting states. By the way, when CFA is nondeterministic (NCFA), it is desirable that the colors of accepting states are unmixed (i.e., there are no inputs that are accepted with differently colored accepting states) in order to pursuit the accurate identification. Thus, the author proposes the three decision problems (Unmixedness Verification problem, Unmixedness Partitioning problem, and Unmixedness Extension problem) concerning unmixedness and show that UV, UP, and UE problems are shown to be NLOG-complete, P, and NP-complete, respectively. The author also illustrates the applications of colored finite automata, e.g. to existing regular expression engines and model checking tools for the purpose of improvement of their efficiency and conveniency.Next, the author introduces "colored pushdown automaton (CPDA)" which is an ordinary pushdown automaton with colored accepting states. It is shown that while the computational complexity of the above-mentioned UV, UP, and UE problems of CPDA are all undecidable, restriction of CPDA are all undecidable, restriction of CPDAs to unambiguous ones simplifies some problems of them to the permanently true problems.In this way, the concept of colored accepting states can be applied to a wide range of automata that have a set of accepting states and expected to be useful in a wide range of theoretical and practical field of automata applications in the future.
Collection (particular)国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文
Date Accepted (W3CDTF)2023-03-03T17:22:19+09:00
Data Provider (Database)国立国会図書館 : 国立国会図書館デジタルコレクション