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
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.
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
Chuzo IWAMOTO, Harumasa YONEDA, Kenichi MORITA, Katsunobu IMAI, "A Recursive Padding Technique on Nondeterministic Cellular Automata" in IEICE TRANSACTIONS on Fundamentals,
vol. E91-A, no. 9, pp. 2335-2340, September 2008, doi: 10.1093/ietfec/e91-a.9.2335.
Abstract: We present a tight time-hierarchy theorem for nondeterministic cellular automata by using a recursive padding argument. It is shown that, if t2(n) is a time-constructible function and t2(n) grows faster than t1(n+1), then there exists a language which can be accepted by a t2(n)-time nondeterministic cellular automaton but not by any t1(n)-time nondeterministic cellular automaton.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.9.2335/_p
Copiar
@ARTICLE{e91-a_9_2335,
author={Chuzo IWAMOTO, Harumasa YONEDA, Kenichi MORITA, Katsunobu IMAI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Recursive Padding Technique on Nondeterministic Cellular Automata},
year={2008},
volume={E91-A},
number={9},
pages={2335-2340},
abstract={We present a tight time-hierarchy theorem for nondeterministic cellular automata by using a recursive padding argument. It is shown that, if t2(n) is a time-constructible function and t2(n) grows faster than t1(n+1), then there exists a language which can be accepted by a t2(n)-time nondeterministic cellular automaton but not by any t1(n)-time nondeterministic cellular automaton.},
keywords={},
doi={10.1093/ietfec/e91-a.9.2335},
ISSN={1745-1337},
month={September},}
Copiar
TY - JOUR
TI - A Recursive Padding Technique on Nondeterministic Cellular Automata
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2335
EP - 2340
AU - Chuzo IWAMOTO
AU - Harumasa YONEDA
AU - Kenichi MORITA
AU - Katsunobu IMAI
PY - 2008
DO - 10.1093/ietfec/e91-a.9.2335
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2008
AB - We present a tight time-hierarchy theorem for nondeterministic cellular automata by using a recursive padding argument. It is shown that, if t2(n) is a time-constructible function and t2(n) grows faster than t1(n+1), then there exists a language which can be accepted by a t2(n)-time nondeterministic cellular automaton but not by any t1(n)-time nondeterministic cellular automaton.
ER -