Maximum order complexity for some automatic and morphic sequences along polynomial values
Pierre Popoli
Institut Élie Cartan de Lorraine, à Nancy
https://sites.google.com/view/pierre-popoli
Date(s) : 27/06/2022 iCal
15h00 - 16h00
Automatic sequences are not suitable sequences for cryptographic applications since both their subword complexity and their expansion complexity are small, and their correlation measure of order 2 is large. These sequences are highly predictable despite having a large maximum order complexity. However, recent results show that polynomial subsequences of automatic sequences, such as the Thue-Morse sequence or the Rudin-Shapiro sequence, are better candidates for pseudorandom sequences. A natural generalization of automatic sequences are morphic sequences, given by a fixed point of a prolongeable morphism that is not necessarily uniform. In this talk, I will present my results on lowers bounds for the maximum order complexity of the Thue-Morse sequence, the Rudin-Shapiro sequence and the sum of digits function in Zeckendorf base, which are respectively automatics and morphic sequences. .
Video and slides here : https://www.i2m.univ-amu.fr/wiki/Combinatorics-on-Words-seminar/
The address of the Zoom meeting is https://zoom.us/j/92245493528 . The password is distributed in announcements. If you want to receive them, or receive them and want to unsubscribe, please write to Anna Frid.
Catégories Pas de Catégories
