A Generalization of Automorphism Classification of Cellular Automata
Hidenosuke Nishio
As a concluding job in a series of studies on the automorphic classification of cellular automata (CA), a generalized automorphism called g-automorphism of CA is defined and investigated, where both of the permutations of the neighborhood and the arguments of the local function are considered. First it is proved that the g-automorphisms constitute a group under semi-direct product. The group acts on the set of local functions and naturally induces a classification of CA such that every CA in a class has the same global properties up to permutation. As a computational example, a complete g-automorphic classification of ECA is given, where all 256 ECA rules are classified into 11 g-automorphism classes and 48 ECA rules are shown g-automorphic to rule 110 or universal up to permutation. This kind of algebraic study of classification must help to understand the mathematical nature of CA as a whole and to find new useful local functions efficiently.
Keywords: cellular automaton, neighborhood, permutation, semi-direct product, automorphism, classification, rule110, ECA