The power of one-letter rational languages
Thierry Cachat
For any language L, let Pow(L)={u^j | j>0, u in L} be the
set of powers of elements of L. Given a rational language L (over a
finite alphabet), we study the question, posed in [Cal 96], whether Pow(L)
is rational or not. While leaving open the problem in general, we provide
an algorithmic solution for the case of one-letter alphabets. This case
is still non trivial; our solution is based on Dirichlet's result that
for two relatively prime numbers, their associated arithmetic progression
contains infinitely many primes.