Changing the Neighborhood of Cellular Automata: Local Structure, Equivalence and Isomorphism
Hidenosuke Nishio and Thomas Worsch
From the definition of a cellular automaton CA (S,Q, f , ν) with S a discrete cellular space, Q a finite set of cell states, f an n-ary local function and ν a neighborhood ν : {1, . . . , n} → S, we pick up a pair (f , ν) and call the local structure of CA.We formulate equivalence of local structures and typically prove that the relationship via a permutation is the only possible way to get equivalence of CA. Next we treat isomorphism of local structures, which is equivalence with re-naming of the cell states. By taking all permutations of the neighborhood, we give a new classification of 256 1-dimensional 2- states nearest neighbors CA (ECA) into 46 isomorphism classes, compared the historical classification of ECA into 88 classes.
Keywords: cellular automaton, local structure, neighborhood, permutation, equivalence, isomorphism, similarity, classification, ECA