Properties of cellular automata on a group

Abstract

A cellular automaton (pl. Cellular Automata(CA)) is a discrete model studied in the fields of Computer science, Mathematics and Theoretical Biology with different purposes such as simulation of natural phenomena and modeling process. A cellular automaton consists of a regular grid of cells. Each cell is represented by on or off state. The dimension of grid can be finite or infinite. The relationship between cellular automata and group theory was studied by T. Ceccherini-Silberstein in 2010. Thereafter, in 2014, S. Inokuchi et al has introduced composition for cellular automata on groups. This study is based on the notion of a cellular automaton and the relation between the cellular automata and groups. We fix a group G and an arbitrary set which is called the alphabet. Then a configuration is defined as a map from the group into the alphabet. The left multiplication in G induces a natural action of G on the set of configurations, which is called the G-shift and all cellular automata will be required to commute with the shift. The memory set of minimal cardinality of cellular automaton is called its minimal memory set. In this research, we prove some properties of cellular automata defined on a group G such as, every cellular automaton is G-equivariant; intersection of two memory sets of a cellular automaton is also a memory set; every bijective cellular automaton is invertible; Cartesian product of two cellular automata is also a cellular automaton. We also find the minimal memory set for some cellular automaton and the number of cellular automata for a finite group.