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