Cobham's Theorem and Automaticity
classification
💻 cs.FL
math.COmath.NT
keywords
sequenceautomaticaperiodicboundscobhamcommontheoremarbitrarily
read the original abstract
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 $a$-automatic sequence and an aperiodic $b$-automatic sequence, where $a$ and $b$ are multiplicatively independent. We also show that an automatic sequence cannot have arbitrarily large factors in common with a Sturmian sequence.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.