Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

A cellular automaton is a discrete dynamical system consisting of cells whose values update according to a local rule.  A sequence s(0), s(1), s(2), ... is called k-automatic if s(n) is a finite-state function of the base-k digits of n.  In 1993 Litow and Dumas found an interesting connection between automatic sequences and cellular automata.  They proved that each column sequence of a linear cellular automaton over a finite field is p-automatic, where p is the characteristic of the field.  The proof is entirely about formal power series and hinges on Furstenberg's theorem that a power series over a finite field is algebraic if and only if it is the diagonal of a rational bivariate series.  Recently, R. Yassawi and I established a converse:  Every p-automatic sequence occurs as a column sequence of a linear cellular automaton with memory.  Together with the Litow-Dumas result, this gives a new characterization of p-automatic sequences.