arXiv Open Access 2025

Density of rational languages under shift invariant measures

Valérie Berthé Herman Goulet-Ouellet Dominique Perrin

Lihat Sumber

Abstrak

We study density of rational languages under shift invariant probability measures on spaces of two-sided infinite words, which generalizes the classical notion of density studied in formal languages and automata theory. The density for 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. We establish the existence of densities for all rational languages under all shift invariant measures. We also give explicit formulas under certain conditions, in particular when the language is aperiodic. Our approach combines tools and ideas from semigroup theory and ergodic theory.

Topik & Kata Kunci

cs.FL

Penulis (3)

Valérie Berthé

Herman Goulet-Ouellet

Dominique Perrin

Format Sitasi

APA MLA BibTeX

Berthé, V., Goulet-Ouellet, H., Perrin, D. (2025). Density of rational languages under shift invariant measures. https://arxiv.org/abs/2504.16708

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2025
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓