A Recursive Padding Technique on Nondeterministic Cellular Automata
Chihiro Iwamoto, H. YONEDA, Kenichi Morita, K. IMAI · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2008
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.