For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Dynamics of Cellular Automata on Groups
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1999/10/25
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>>
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.