Skip to main content

On the pseudorandomness of automatic sequences

Posted in
László Mérai
Johann Radon Inst. for Computational and Applied Mathematics, Austrian Academy of Sciences, Linz, Austria
Wed, 2017-04-26 16:30 - 17:30
MPIM Lecture Hall
Parent event: 
Number theory lunch seminar

A sequence $(s_n)$ is called p-automatic if the n-th term of the sequence $s_n$ is the
output of a fi nite automaton when the input is the p-ary expansion of n. Classical examples
for 2-automatic sequences are the Thue-Morse and the Rudin-Shapiro sequences.
In this talk I am going to speak about some properties of pseudorandomness of automatic
sequences. On the one hand these sequences are close to random sequences in terms of
linear complexity. On the other hand these sequences are as far from random sequences
as possible in terms of correlation measure. Thus these sequences are the fi rst examples
which have good linear complexity but bad correlation measure.

© MPI f. Mathematik, Bonn Impressum
-A A +A