The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Beberapa buku teks bahasa formal dan teori automata secara tersirat menyatakan kesamaan struktur binari n-graf de Bruijn berdimensi dan gambar rajah keadaan automata terhingga penentu keadaan minimum yang menerima bahasa biasa (0+1)*1(0+1)n-1. Dengan memperkenalkan automata terhingga khas yang keadaan penerimaannya diperhalusi dengan dua atau lebih warna, kami memanjangkan fakta ini kepada kedua-duanya kversi -ary. Maksudnya, kita buktikan k-sampai n-graf de Brujin dimensi dan rajah keadaan untuk automata terhingga berwarna deterministik keadaan minimum yang menerima (k-1)-tuple bahasa biasa (0+1+…+k-1)*1(0+1+…+k-1)n-1,...,dan(0+1+…+k-1)*(k-1)(0+1+…+k-1)n-1 adalah isomorfik untuk sewenang-wenangnya k lebih daripada atau sama dengan 2. Kami juga menyiasat sifat automata terhingga berwarna itu sendiri dan memberikan keputusan kerumitan pengiraan pada tiga masalah keputusan mengenai ketidakcampuran warna bagi yang tidak tentu.
Yoshiaki TAKAHASHI
Oshima College
Akira ITO
Yamaguchi University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Yoshiaki TAKAHASHI, Akira ITO, "Finite Automata with Colored Accepting States and Their Unmixedness Problems" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 3, pp. 491-502, March 2022, doi: 10.1587/transinf.2021FCP0012.
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. 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021FCP0012/_p
Salinan
@ARTICLE{e105-d_3_491,
author={Yoshiaki TAKAHASHI, Akira ITO, },
journal={IEICE TRANSACTIONS on Information},
title={Finite Automata with Colored Accepting States and Their Unmixedness Problems},
year={2022},
volume={E105-D},
number={3},
pages={491-502},
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. 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.},
keywords={},
doi={10.1587/transinf.2021FCP0012},
ISSN={1745-1361},
month={March},}
Salinan
TY - JOUR
TI - Finite Automata with Colored Accepting States and Their Unmixedness Problems
T2 - IEICE TRANSACTIONS on Information
SP - 491
EP - 502
AU - Yoshiaki TAKAHASHI
AU - Akira ITO
PY - 2022
DO - 10.1587/transinf.2021FCP0012
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2022
AB - 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.
ER -