A Time Hierarchy Theorem for 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 non-deterministic cellular automaton.