Index Permutations and Classes of Additive Cellular Automata Rules with Isomorphic STD
Valeriy Bulitko and Burton Voorhees
First we consider the question of identifying linear transformations that transform any additive CA rule into an additive CA rule with an isomorphic STD. A general condition is derived. Following on this, we consider a subclass of such transformations (index permutations). This allows, on one hand, a complete description and on the other hand, generalization of the results for the class of linear rules. Then the case of binary valued 1-dimensional additive cellular automata (d = 1, p = 2) and classes of isomorphisms of STDs that contain only a single rule (singletons) are considered. It is shown how singletons can be used to extend known systems of isomorphic STD classes. Finally we study how the baker transformation provides information about singletons and, by using this, present an algorithm that generates all singletons for one-dimensional additive CA of odd sizes.
Keywords: Additive cellular automata, state transition diagram, discrete baker transformation, isomorphic classes.