In this talk, I will present recent results, obtained in collaboration with Valérie Berthé and Dominique Perrin, on the density of rational languages under shift invariant probability measures on spaces of two-sided infinite words. This notion of density generalizes a classical notion of density studied in formal languages and automata theory. The density of a language is defined as the limit in average (if it exists) of the probability that a word of a given length belongs to the language. I will explain how we establish the existence of densities for all rational languages under all shift invariant measures using tools from ergodic theory, and how the proof leads to explicit formulas under certain conditions.
Date and Venue
Start Date
Venue
Online Zoom Meeting
End Date
Speaker
Herman Goulet-Ouellet
Speaker's Institution
Czech Technical University
Files
semLP_0.pdf116.62 KB
Area
Semigroups, Automata and Languages