pith. sign in

arxiv: 1809.00679 · v2 · pith:TILMAWWNnew · submitted 2018-09-03 · 💻 cs.FL · math.CO· math.NT

Cobham's Theorem and Automaticity

classification 💻 cs.FL math.COmath.NT
keywords sequenceautomaticaperiodicboundscobhamcommontheoremarbitrarily
0
0 comments X
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.