Abstract :
[en] Generalizations of numeration systems in which \(\N\) is recognizable by a finite automaton are obtained by describing a lexicographically ordered infinite regular language \(L\subset \Sigma^*\). For these systems, we obtain a characterization of recognizable sets of integers in terms of $\N$-rational formal series. After a study of the polynomial regular languages, we show that, if the complexity of \(L\) is \(\Theta (n^l)\) (resp. if \(L\) is the complement of a polynomial language), then multiplication by \(\lambda\in \N\) preserves recognizability only if \(\lambda=\beta^{l+1}\) (resp. if \(\lambda\neq (\#\Sigma)^\beta\)) for some \(\beta\in \N\). Finally, we obtain sufficient conditions for the notions of recognizability for abstract systems and some positional number systems to be equivalent.
Scopus citations®
without self-citations
6