A study on automata with colored accepting states and their unmixedness problems

色付き受理状態を持つオートマタとそれらの非混色性問題に関する研究

A study on automata with colored accepting states and their unmixedness problems

Degree Grantors Yamaguchi University

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.

Creators 高橋 芳明