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.
last update: 27.9.2007, webmaster: Petr Ambrož