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.
- （社）電子情報通信学会の論文
- 2008-09-01
著者
-
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
-
Iwamoto Chuzo
Hiroshima Univ. Higashihiroshima‐shi Jpn
-
Iwamoto Chuzo
Graduate School Of Engineering Hiroshima University
-
Morita Kenichi
Hiroshima Univ. Higashihiroshima‐shi Jpn
-
Morita K
Hiroshima Univ. Higashi‐hiroshima‐shi Jpn
-
Morita Kenichi
Graduate School Of Engineering Hiroshima University
-
Imai K
Graduate School Of Engineering Hiroshima University
-
Imai Katsunobu
Graduate School Of Engineering Hiroshima University
-
Yoneda Harumasa
Graduate School Of Engineering Hiroshima University
関連論文
- A Recursive Padding Technique on Nondeterministic Cellular Automata
- NP-Hard and k-EXPSPACE-Hard Cast Puzzles
- Uniquely Parallel Parsable Unification Grammars (Special lssue on Selected Papers from LA Synposium)
- Normal Forms for Uniquely Parsable Grammar Classes Forming the Deterministic Chomsky Hierarchy
- 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
- Generalized Shisen-Sho is NP-Complete
- Lower Bound of Face Guards of Polyhedral Terrains
- Generalized Chat Noir is PSPACE-Complete