A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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

Finite Automata with Colored Accepting States and Their Unmixedness Problems Autômatos Finitos com Estados de Aceitação Coloridos e Seus Problemas de Não Mistura

Yoshiaki TAKAHASHI, Akira ITO

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

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.

Publicação
IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.491-502
Data de publicação
2022/03/01
Publicitada
2021/11/01
ISSN online
1745-1361
DOI
10.1587/transinf.2021FCP0012
Tipo de Manuscrito
Special Section PAPER (Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -)
Categoria

autores

Yoshiaki TAKAHASHI
  Oshima College
Akira ITO
  Yamaguchi University

Palavra-chave