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
Alguns livros didáticos de linguagens formais e teoria dos autômatos afirmam implicitamente a igualdade estrutural do binário nGráfico -dimensional de Bruijn e o diagrama de estado do autômato finito determinístico de estado mínimo que aceita linguagem regular (0+1)*1 (0 + 1)n-1. Ao introduzir autômatos finitos especiais cujos estados de aceitação são refinados com duas ou mais cores, estendemos esse fato a ambos kversões -ary. Ou seja, provamos que k-ário ngráfico -dimensional de Brujin e o diagrama de estado para autômato finito colorido determinístico de estado mínimo que aceita o (k-1)-tupla das linguagens regulares (0+1+…+k-1)*1(0+1+…+k-1)n-1,...,e(0+1+…+k-1)*(k-1)(0+1+…+k-1)n-1 são isomórficos para arbitrários k maior ou igual a 2. Também investigamos as propriedades dos próprios autômatos finitos coloridos e fornecemos resultados de complexidade computacional em três problemas de decisão relativos à não mistura de cores de autômatos não determinísticos.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -