On one-way cellular automata with a fixed number of cells
- We investigate a restricted one-way cellular automaton (OCA) model where the number of cells is bounded by a constant number k, so-called kC-OCAs. In contrast to the general model, the generative capacity of the restricted model is reduced to the set of regular languages. A kC-OCA can be algorithmically converted to a deterministic finite automaton (DFA). The blow-up in the number of states is bounded by a polynomial of degree k. We can exhibit a family of unary languages which shows that this upper bound is tight in order of magnitude. We then study upper and lower bounds for the trade-off when converting DFAs to kC-OCAs. We show that there are regular languages where the use of kC-OCAs cannot reduce the number of states when compared to DFAs. We then investigate trade-offs between kC-OCAs with different numbers of cells and finally treat the problem of minimizing a given kC-OCA.
| Verfasserangaben: | Andreas Malcher |
|---|---|
| URN: | urn:nbn:de:hebis:30-71706 |
| ISSN: | 1616-9107 |
| Titel des übergeordneten Werkes (Deutsch): | Frankfurter Informatik-Berichte ; Nr. 03,1 |
| Schriftenreihe (Bandnummer): | Frankfurter Informatik-Berichte (03, 1) |
| Verlag: | Johann Wolfgang Goethe-Univ., Fachbereich Biologie und Informatik, Inst. für Informatik |
| Verlagsort: | Frankfurt am Main |
| Dokumentart: | Arbeitspapier |
| Sprache: | Englisch |
| Jahr der Fertigstellung: | 2003 |
| Jahr der Erstveröffentlichung: | 2003 |
| Veröffentlichende Institution: | Universitätsbibliothek Johann Christian Senckenberg |
| Datum der Freischaltung: | 16.10.2009 |
| GND-Schlagwort: | Zellularer Automat |
| Seitenzahl: | IV, 15 S. |
| HeBIS-PPN: | 219731489 |
| Institute: | Informatik und Mathematik / Informatik |
| DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
| Lizenz (Deutsch): |  Deutsches Urheberrecht |
