Combinatorical and Algebraic Structures Seminar

Session details

Date: 20.10.2005
Speaker: Pierre-Adrien TAHAY, FJFI, České vysoké učení technické v Praze
Title: Construction of some sequences by cellular automata
Abstract: Finite automata are one of the most basic models of computation. A sequence $(u_n)_{n\geq 0}$ such that $u_n$ can be computed by a finite automaton with the base-$k$ representation of $n$ is called $k$-automatic sequence. On the other hand, cellular automata are dynamical systems defined by a local rule wich acts uniformly and synchronously on the configuration space. In 2015, Rowland and Yassawi established a link between these two ob- jects. They showed that, if $p$ is a prime number, the columns of linear cellular automata are $p$-automatic sequences and conversly all $p$-automatic sequences can be realized by some linear cellular automaton with memory. Moreover, they provide a constructive method to generated a given $p$-automatic sequences by an explicit cellular automaton. In this talk, I will present several constructions of $p$-automatic sequences by linear cellular automata, in particular the characteristic function of the set of sums of three squares which is a 2-automatic sequence, and some constructions of nonautomatic sequences by nonlinear cellular automata, such that the characteristic function of the squares, which is an emblematic nonautomatic sequence.

Return to index.