IEICE TRANSACTIONS on Fundamentals
A Recursive Padding Technique on Nondeterministic Cellular Automata
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.9 pp.2335-2340
- Publication Date
- 2008/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e91-a.9.2335
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
