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
우리는 재귀 패딩 인수를 사용하여 비결정적 셀룰러 오토마타에 대한 엄격한 시간 계층 정리를 제시합니다. 다음과 같이 표시됩니다. t2(n)는 시간 구성 함수이고 t2(n)보다 빠르게 성장 t1(n+1) 그러면 다음과 같은 언어가 허용될 수 있습니다. t2(n)-시간 비결정적 세포 자동 장치이지만 어떤 것도 아님 t1(n)-시간 비결정적 세포 자동 장치.
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.
부
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
부
@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},}
부
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 -