Changing the Neighborhood of Cellular Automata: Local Structure, Equivalence and Isomorphism

From the definition of a cellular automaton CA (S,Q, f, v) with S a discrete cellular space, Q a finite set of cell states, f an n-ary local function and v a neighborhood v : (l, ... , n} -> S, we pick up a pair (f, v) 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.