Deterministic pushdown automata can compress some normal sequences

Orateur : Sylvain Perifel
30 Mai 2023 à 14:00 ; lieu : Seminar room 4B125 (Copernic building)

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 same length have the same frequency. Normality can also be characterized by non-compressibility by finite state machines. In this talk we will show that pushdown machines, even deterministic, can compress some normal sequences. This solves positively a question left open by V. Becher, P. A. Heiber and O. Carton. Joint work with O. Carton


Seminar room 4B125 (Copernic building)

5 Boulevard Descartes 77420 Champs-sur-Marne