Maximum order complexity for some automatic and morphic sequences along polynomial values
Pierre Popoli (Université de Lorraine)
Abstract: 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.
dynamical systemsnumber theory
Audience: researchers in the topic
Series comments: Description: Online seminar on numeration systems and related topics
For questions or subscribing to the mailing list, contact the organisers at numeration@irif.fr
| Organizers: | Shigeki Akiyama, Ayreena Bakhtawar, Karma Dajani, Kevin Hare, Hajime Kaneko, Niels Langeveld, Lingmin Liao, Wolfgang Steiner* |
| *contact for this listing |