On a Conjecture of J.Shallit

摘要

We solve a conjecture of J. Shallit related to the automaticity function of a unary language,or equivalently to the first occurrence function in a symbolic sequence. The answer is negative: the conjecture is false, but it can be corrected by changing the constantinvolved. The proof is based on a study of paths in the Rauzy graphs associated with the sequence.