Contents Menu

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

DT15100103_Abstract.pdf
[abstract] 5.06 MB
DT15100103_Fulltext.pdf
[fulltext] 18.3 MB
Title
色付き受理状態を持つオートマタとそれらの非混色性問題に関する研究
A study on automata with colored accepting states and their unmixedness problems
Degree 博士(工学) Dissertation Number 創科博甲第103号 (2022-11-02)
Degree Grantors Yamaguchi University
[kakenhi]15501 grid.268397.1
Abstract
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 高橋 芳明
Languages jpn
Resource Type doctoral thesis
File Version Version of Record
Access Rights open access