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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Andreas Malcher
URN:urn:nbn:de:hebis:30-71706
ISSN:1616-9107
Parent Title (German):Frankfurter Informatik-Berichte ; Nr. 03,1
Series (Serial Number):Frankfurter Informatik-Berichte (03, 1)
Publisher: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:2003
Year of first Publication:2003
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2009/10/16
GND Keyword:Zellularer Automat
Page Number:IV, 15 S.
HeBIS-PPN:219731489
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