Cellular Automata as Cycoltomic Polynomials presented at the 2008 Automata Conference in Bristol, England, July 12-14, 2008

Abstract

One dimensional binary valued cylindrical cellular automata can be represented as polynomials in roots of unity. Doing so allows several advantages over the more conventional representation as dipolynomials and connects directly with representation as circulant matrices. In addition, this allows easy classification of these cellular automata into equivalence classes based on permutations of eigenvalues of the associated circulant matrix. We show that these permutations also preserve state transition diagrams, connecting with recent more general work on rules with isomorphic state transition diagrams.