Dynamics of Cellular Automata on Groups

Shuichi YUKITA  

IEICE TRANSACTIONS on Information and Systems   Vol.E82-D   No.10   pp.1316-1323
Publication Date: 1999/10/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automata,Languages and Theory of Computing
cellular automata on groups,  tessellations,  Cayley graphs,  periods,  residually finite groups,  

Full Text: PDF>>
Buy this Article

Dynamical theory of cellular automata on groups is developed. Main results are non-Euclidean extensions of Sato and Honda's results on the dynamics of Euclidean cellular automata. The notion of the period of a configuration is redefined in a more group theoretical way. The notion of a co-finite configuration substitutes the notion of a periodic configuration, where the new term is given to it to reflect and emphasize the importance of finiteness involved. With these extended or substituted notions, the relations among period preservablity, injectivity, and Poisson stability of parallel maps are established. Residually finite groups are shown to give a nice topological property that co-finite configurations are dense in the configuration space.