Measuring Power of Commutative 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\) . In this paper, we investigate the measuring powers of \(\textsf{Gcom}\) of the class of all languages recognised by finite commutative groups and its subclass named \(\textsf{MOD}\) . A language is in \(\textsf{MOD}\) if membership of a word in the language only depends on its length modulo some fixed integer. In particular, we show that, for a given regular language \(L\) , it is decidable whether \(L\) is \(\textsf{Gcom}\) -measurable ( \(\textsf{MOD}\) -measurable, respectively) or not. Our results demonstrate that there is a huge gap between the expressive power of group languages and commutative group languages, even from a (very rough) measure theoretic point of view.