Descriptional complexity of cellular automata and decidability questions

  • 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 realtime-OCA. 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 so-called nonrecursive trade-off. Furthermore, nonrecursive trade-offs are shown between some restricted classes of cellular automata. The set of valid computations of a Turing machine can be recognized by a realtime-OCA. 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Andreas Malcher
Parent Title (German):Frankfurter Informatik-Berichte ; Nr. 01,04
Series (Serial Number):Frankfurter Informatik-Berichte (01, 4)
Publisher:Frankfurt am Main : Johann Wolfgang Goethe-Univ., Fachbereich Biologie und Informatik, Inst. für Informatik
Place of publication:Frankfurt am Main
Document Type:Working Paper
Year of Completion:2001
Year of first Publication:2001
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2009/10/16
Page Number:11, IV S.
Institutes:Informatik und Mathematik / Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Licence (German):License LogoDeutsches Urheberrecht