Cobham's theorem for substitutions

DOI10.4171/JEMS/294zbMATH Open1246.11073arXiv1010.4009OpenAlexW2963417818MaRDI QIDQ645357FDOQ645357

Fabien Durand

Publication date: 14 November 2011

Published in: Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

Abstract: The seminal theorem of Cobham has given rise during the last 40 years to a lot of works around non-standard numeration systems and has been extended to many contexts. In this paper, as a result of fifteen years of improvements, we obtain a complete and general version for the so-called substitutive sequences. Let $alpha$ and $$ be two multiplicatively independent Perron numbers. Then, a sequence $xin{A}^{m}athbbN$, where $A$ is a finite alphabet, is both $alpha$-substitutive and $$-substitutive if and only if $x$ is ultimately periodic.

Full work available at URL: https://arxiv.org/abs/1010.4009

zbMATH Keywords

return wordsCobham's theoremsubstitutive sequence

Mathematics Subject Classification ID

Combinatorics on words (68R15) Automata sequences (11B85)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The ring of \(k\)-regular sequences
• Automatic Sequences
• An analogue of Cobham’s theorem for fractals
• Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem
• Function fields in positive characteristic: expansions and Cobham's theorem
• A generalization of Cobham's theorem for regular sequences
• On the Sets of Real Numbers Recognized by Finite Automata in Multiple Bases
• An extension of the Cobham-Semënov Theorem
• A Generalization of Cobham’s Theorem to Automata over Real Numbers

Cited In (23)

• Dynamics of interval maps generated by erasing substitutions
• Morphic sequences versus automatic sequences
• Mixing properties of erasing interval maps
• A conjecture of Dekking on the dimensions of the lower central series factors of a certain just infinite Lie algebra
• Asymptotic properties of free monoid morphisms
• From Combinatorial Games to Shape-Symmetric Morphisms
• Hyperquadratic continued fractions and automatic sequences
• On Multiplicative Independent Bases for Canonical Number Systems in Cyclotomic Number Fields
• How to prove that a sequence is not automatic
• Mixing properties and entropy bounds of a family of Pisot random substitutions
• An asymptotic version of Cobham’s theorem
• The Formal Inverse of the Period-Doubling Sequence
• Quantitative estimates for the size of an intersection of sparse automatic sets
• Consistent systems of linear differential and difference equations
• Sum-free sets generated by the period-\(k\)-folding sequences and some Sturmian sequences
• Rigidity and Substitutive Dendric Words
• Hidden automatic sequences
• Substitutive systems and a finitary version of Cobham's theorem
• On automatic subsets of the Gaussian integers
• Decidability of uniform recurrence of morphic sequences
• An analogue of Cobham's theorem for graph directed iterated function systems
• On some conjectures of P. Barry
• Proving results about OEIS sequences with \texttt{Walnut}

This page was built for publication: Cobham's theorem for substitutions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q645357)