Note: [] Address for correspondence: Kyoto University, Iwakura Miyake-cho 204-1, Sakyo-ku, 606-0022, Kyoto, Japan
Abstract: A new classification of arbitrary cellular automata (CA for short) in Zd is studied considering the set (group) of all permutations of the neighborhood ν and state set Q. Two CA (Zd, Q, fA, νA) and (Zd, Q, fB, νB) are called automorphisc, if there is a pair of permutations (π, �) of ν and Q, respectively, such that (fB, ν B) = (�−1 fAπ�, νAπ), where νπ denotes a permutation of ν and fπ denotes a permutation of arguments of local function f corresponding to ν π. This automorphissm naturally induces a classification of CA, such that it generally preserves the global properties of CA up to permutation. As a typical example of the theory, the local functions of 256 ECA (1-dimensional 3-nearest neighbors 2-states CA) are classified into 46 classes. We also give a computer test of surjectivity, injecitivity and reversibility of the classes.
Keywords: cellular automaton, automorphissm, classification, permutation, neighborhood, group action, ECA
