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

• Autorzy: Malcher A.
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

cellular automata; descriptional complexity; regular language

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 58, nr 3,4
• Strony: 355--368
• Opis fizyczny: Bibliogr. 7 poz., tab.

Twórcy

autor

Malcher A.

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

Bibliografia

• [1] Goldstine, J., Kappes, M., Kintala, C. M. R., Leung, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. J.UCS, 8(2), 2002, 193-234.
• [2] Hopcroft, J. E.: An n log n algorithm for minimizing states in a finite automaton, in: Theory of machines and computations (Z. Kohavi, Ed.). Academic Press, New York, 1971, 189-196.
• [3] Hopcroft, J. E., Ullman, J. D.: Introduction to automata theory, languages, and computation. Addison-Wesley Publishing Co., Reading, Mass., 1979.
• [4] Kutrib, M.: Automata arrays and context-free languages, in: Where Mathematics, Computer Science, Linguistics and Biology Meet (C. Marlin-Vide, V. Mitrana, Eds.), Kluwer Academic Publishers. Dordrecht, 2001, 139-148.
• [5] Malcher, A.: Descriptional complexity of cellular automata and decidability questions, J. Autom. Lang. Comb., 7(4), 2002, 549-560.
• [6] Meyer, A. R., Fischer, M. J.: Economy of Description by Automata, Grammars, and Formal Systems, in: IEEE Twelfth Annual Symposium on Switching and Automata Theory, IEEE. 1971, 188-191.
• [7] Seidel. S. R.: Language recognition and the synchronization of cellular automata. Technical Report 79-02, Department of Computer Science, University of Iowa. 1979.