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

A Recursive Padding Technique on Nondeterministic Cellular Automata Uma técnica de preenchimento recursivo em autômatos celulares não determinísticos

Chuzo IWAMOTO, Harumasa YONEDA, Kenichi MORITA, Katsunobu IMAI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Apresentamos um teorema de hierarquia de tempo rígido para autômatos celulares não determinísticos usando um argumento de preenchimento recursivo. Mostra-se que, se t2(n) é uma função construtível no tempo e t2(n) cresce mais rápido que t1(n+1), então existe uma linguagem que pode ser aceita por um t2(n)-tempo autômato celular não determinístico, mas não por qualquer t1(n)-tempo autômato celular não determinístico.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.9 pp.2335-2340
Data de publicação
2008/09/01
Publicitada
ISSN online
1745-1337
DOI
10.1093/ietfec/e91-a.9.2335
Tipo de Manuscrito
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Categoria

autores

Palavra-chave