Links between normality and automata

Normality has been introduced by É. Borel more than one hundred years ago. A real number is normal to an integer base if, in its infinite expansion expressed in that base, all blocks of digits of the same length have the same limiting frequency. Normality formalizes the least requirements about a random sequence. In this talk, we explain several links between this notion and finite-state machines. This includes the characterization of normality by non-compressibility, preservation of normality by selection and computing frequencies with weighted automata.

 

Date and Venue

Start Date
Venue
Online Zoom meeting
End Date

Speaker

Olivier Carton

Speaker's Institution

Université de Paris

Files

Area

Semigroups, Automata and Languages

Financiamento