The search functionality is under construction.
The search functionality is under construction.

Finite Automata with Colored Accepting States and Their Unmixedness Problems

Yoshiaki TAKAHASHI, Akira ITO

  • Full Text Views

    0

  • Cite this

Summary :

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. By introducing special finite automata whose accepting states are refined with two or more colors, we extend this fact to both k-ary versions. That is, we prove that k-ary n-dimensional de Brujin graph and the state diagram for minimum state deterministic colored finite automaton which accepts the (k-1)-tuple of the regular languages (0+1+…+k-1)*1(0+1+…+k-1)n-1,...,and(0+1+…+k-1)*(k-1)(0+1+…+k-1)n-1 are isomorphic for arbitrary k more than or equal to 2. We also investigate the properties of colored finite automata themselves and give computational complexity results on three decision problems concerning color unmixedness of nondeterminisitic ones.

Publication
IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.491-502
Publication Date
2022/03/01
Publicized
2021/11/01
Online ISSN
1745-1361
DOI
10.1587/transinf.2021FCP0012
Type of Manuscript
Special Section PAPER (Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -)
Category

Authors

Yoshiaki TAKAHASHI
  Oshima College
Akira ITO
  Yamaguchi University

Keyword