Deterministic pushdown automata can compress some normal sequences

Orateur : Sylvain Perifel
30 Mai 2023 à 14:00 ; lieu : Salle de séminaire 4B125 (bâtiment Copernic)

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


Salle de séminaire 4B125 (bâtiment Copernic)

5 Boulevard Descartes 77420 Champs-sur-Marne