Cobham’s Theorem and Automaticity
Lucas Mol, Narad Rampersad, Jeffrey O. Shallit, Manon Stipulanti · International Journal of Foundations of Computer Science · 2019
We make certain bounds in Krebs’ proof of Cobham’s theorem explicit and obtain corresponding upper bounds on the length of a common prefix of an aperiodic [Formula: see text]-automatic sequence and an aperiodic [Formula: see text]-automatic sequence, where [Formula: see text] and [Formula: see text] are multiplicatively independent. We also show that an automatic sequence cannot have arbitrarily large factors in common with a Sturmian sequence.