An algorithm for testing permutativeness of cellular automata (Q732363)

The paper aims at giving a procedure to decide, based on the local rule of a given cellular automaton, whether or not it is a permutation cellular automaton. With respect to this the authors elaborate a testing algorithm based on the so-called uniformly extendable block and minimally uniformly extendable block which generates test words identifying the permutativeness by producing simultaneously the inducing code and the permutation set. Two necessary and sufficient conditions for permutativeness are given. The testing algorithm is illustrated on permutativeness of elementary cellular automata.