Skip to Main content Skip to Navigation
New interface

Colonnes dans les automates cellulaires et suites généralisées de Rudin-Shapiro

Abstract : This thesis is at the interface between mathematics and theoretical computer science. In the first part, our main objects are finite automata and cellular automata. While relatively different in nature, it is possible to link both by explicit constructions. More specifically, it is possible to realise automatic sequences in the space-time diagrams of cellular automata. In the second part, we study discrete correlation properties of so-called generalised Rudin–Shapiro sequences. These are automatic sequences, hence deterministic, but show similar properties as random sequences with respect to their discrete correlation of order 2. After introducing the objects of study, illustrated by several examples, we first recall the result of Rowland and Yassawi. They showed in 2015 via an algebraic approach that it is possible to construct explicitly any p-automatic sequence (p is a prime number) as a column of a linear cellular automaton with a finite initial configuration. By using their method, we obtain several constructions of classical automatic sequences, and an explicit way to build a family of p-automatic sequences that we study in a more general context in the second part of the thesis. We also investigate several non-automatic sequences, such as the characteristic sequence of integer-valued polynomials and the Fibonacci word, which both can be realised as columns of non-linear cellular automata. We end this part by some results about binary recodings in order to reduce the number of symbols in the cellular automata. Under a binary recoding, we give explicitly a 3-automatic sequence on a binary alphabet, as a column of a cellular automaton with 2 states, that is not eventually periodic. This answers a question asked by Rowland et Yassawi. In the second part of the thesis, we take up research from 2009 of Grant, Shallit, and Stoll about discrete correlations of infinite sequences over finite alphabets. By using the recursivity properties of the classical Rudin–Shapiro sequence, they built a family of deterministic sequences over larger alpha- bets, called generalised Rudin–Shapiro sequences, for which they showed that when the size of the alphabet is squarefree, the empirical means of the discrete correlation coefficients of order 2 have the same limit as in the case of random sequences where each letter is independently and uniformly chosen. Moreover, they gave explicit error terms. We extend their construction by means of difference matrices and establish a similar result on alphabets of arbitrary size. On our way, we obtain an improvement of the error term in some cases. The methods stem, as those used by Grant et al., from the theory of exponential sums. In the third part, we use a more direct combinatorial approach to study correlations. This allows for an improvement of the error term when the size of the alphabet is a product of at least two distinct primes, and allows to generalise some of our results of the second part.
Document type :
Complete list of metadata
Contributor : Thèses UL Connect in order to contact the contributor
Submitted on : Monday, March 29, 2021 - 3:21:17 PM
Last modification on : Wednesday, November 3, 2021 - 7:10:33 AM
Long-term archiving on: : Wednesday, June 30, 2021 - 6:41:16 PM


Files produced by the author(s)


  • HAL Id : tel-03184510, version 1


Pierre-Adrien Tahay. Colonnes dans les automates cellulaires et suites généralisées de Rudin-Shapiro. Mathématiques [math]. Université de Lorraine, 2020. Français. ⟨NNT : 2020LORR0198⟩. ⟨tel-03184510⟩



Record views


Files downloads