sigma-automata and Chebyshev-polynomials

摘要

A sigma-automaton is an additive, binary cellular automaton on a graph. For product graphs such as a grids and cylinders, reversibility and periodicity properties of the corresponding sigma-automaton can be expressed in terms of a binary version of Chebyshev polynomials. We will give a detailed analysis of the divisibility properties of these polynomials and apply our results to the study of sigma-automata. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 18]