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.