On One-Way Cellular Automata with a Fixed Number of Cells

Issue title: Cellular Automata

Article type: Research Article

Authors: Malcher, Andreas

Affiliations: Institut für Informatik, Johann Wolfgang Goethe-Universität, Robert-Mayer-Strasse 11-15, D-60054 Frankfurt am Main, Germany

Abstract: 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.

Keywords: cellular automata, descriptional complexity, regular languages

Journal: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 355-368, 2003