A Recursive Padding Technique on Nondeterministic Cellular Automata

摘要

We present a tight time-hierarchy theorem for nondeterministic cellular automata by using a recursive padding argument. It is shown that, if t_2(n) is a time-constructible function and t_2(n) grows faster than t_1(n +1), then there exists a language which can be accepted by a t_2(n)-time nondeterministic cellular automaton but not by any t_1(n)-time nondeterministic cellular automaton.