Pierre Popoli

Pierre Popoli, Université de Lorraine, Nancy

Maximum order complexity for some automatic and morphic sequences along polynomial values

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, are better candidates for pseudorandom
sequences. A natural generalization of automatic sequences are morphic sequences, given by a fixed point of a
prolongable 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 and the sum of digits function in Zeckendorf
base, which are respectively an automatic and a morphic sequence.