Frankfurter InformatikBerichte
1 search hit
 01, 4

Descriptional complexity of cellular automata and decidability questions
(2001)

Andreas Malcher
 We study the descriptional complexity of cellular automata (CA), a parallel model of computation. We show that between one of the simplest cellular models, the realtimeOCA. and "classical" models like deterministic finite automata (DFA) or pushdown automata (PDA), there will be savings concerning the size of description not bounded by any recursive function, a socalled nonrecursive tradeoff. Furthermore, nonrecursive tradeoffs are shown between some restricted classes of cellular automata. The set of valid computations of a Turing machine can be recognized by a realtimeOCA. This implies that many decidability questions are not even semi decidable for cellular automata. There is no pumping lemma and no minimization algorithm for cellular automata.