Measure-Theoretic Aspects of Star-Free and Group Languages

A language $L$ is said to be $\mathcal{C}$-measurable, where $\mathcal{C}$ is a class of languages, if there is an infinite sequence of languages in $\mathcal{C}$ that converges'' to $L$. We investigate the properties of ${\cal C}$-measurability in the cases where ${\cal C}$ is SF, the class of all star-free languages, and G, the class of all group languages. It is shown that a language $L$ is SF-measurable if and only if $L$ is GD-measurable, where GD is the class of all generalised definite languages (a more restricted subclass of star-free languages). This means that GD and SF have the same measuring power’', whereas GD is a very restricted proper subclass of SF. Moreover, we give a purely algebraic characterisation of SF-measurable regular languages, which is a natural extension of Schutzenberger’s theorem stating the correspondence between star-free languages and aperiodic monoids. We also show the probabilistic independence of star-free and group languages, which is an important application of the former result. Finally, while the measuring power of star-free and generalised definite languages are equal, we show that the situation is rather opposite for subclasses of group languages as follows. For any two local subvarieties $\mathcal{C}⊊\mathcal{D}$ of group languages, we have $\{L\mid L\text{ is }\mathcal{C}\text{-measurable}\}⊊\{L\mid L\text{ is }\mathcal{D}\text{-measurable}\}$.