On invertible cellular automata. (English) Zbl 0657.68053

Culik, Karel II

Complex Syst. 1, No. 6, 1035-1044 (1987).

The injectivity of the global transition functions defined by a cellular automata (CA) was studied by S. Amoroso and Y. N. Patt [J. Comput. Syst. Sci. 6, 448-464 (1972; Zbl 0263.94019)], the reviewer [On the theory of the homogeneous structures, Estonian Academic Press (Tallinn 1972; Zbl 0243.94015)], the reviewer, A. Krasnoproshina and V. Kryscanovskij [PARCELLA-88, Math. Res. 48, 33-49 (1988)], and other works. In the present paper a number of results of these works receive an alternative automata theoretic proofs for case of 1- dimensional CA’s, and some related results in this direction are presented.

Reviewer: V.Alad’ev

MSC:

68Q80

Cellular automata (computational aspects)

Keywords:

cellular automata; homogeneous structures

Citations:

Zbl 0263.94019; Zbl 0243.94015