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 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.
著者
-
IWAMOTO Chuzo
Graduate School of Engineering, Hiroshima University
-
YONEDA Harumasa
Graduate School of Engineering, Hiroshima University
-
MORITA Kenichi
Graduate School of Engineering, Hiroshima University
-
IMAI Katsunobu
Graduate School of Engineering, Hiroshima University
関連論文
- A Recursive Padding Technique on Nondeterministic Cellular Automata
- NP-Hard and k-EXPSPACE-Hard Cast Puzzles
- On the Non-existance of Rotation-Symmetric von Neumann Neighbor Number-Conserving Cellular Automata of Which the State Number is Less than Four
- A Recursive Padding Technique on Nondeterministic Cellular Automata
- Prefix Computations on Iterative Arrays with Sequential Input/Output Mode(Cellular Automata)
- A Logically Universal Number-Conserving Cellular Automaton with a Unary Table-Lookup Function(Cellular Automata)
- Time and Space Complexity Classes of Hyperbolic Cellular Automata(Cellular Automata)
- NP-Hard and k-EXPSPACE-Hard Cast Puzzles