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.
| Author: | Andreas Malcher |
|---|---|
| URN: | urn:nbn:de:hebis:30-71662 |
| ISSN: | 1616-9107 |
| 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 |
| Language: | English |
| 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. |
| HeBIS-PPN: | 219724970 |
| Institutes: | Informatik und Mathematik / Informatik |
| Dewey Decimal Classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
| Licence (German): |  Deutsches Urheberrecht |
