Cobham's theorem for substitutions

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

Authors: 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

Recommendations

• A theorem of Cobham for non-primitive substitutions
• A short proof of a theorem of Cobham on substitutions
• scientific article; zbMATH DE number 1984012
• A generalization of Cobham's theorem
• Une généralisation du théorème de Cobham

zbMATH Keywords

return wordsCobham's theoremsubstitutive sequence

Mathematics Subject Classification ID

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

Cites Work

• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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 (28)

• 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
• Rigidity and substitutive dendric words
• Hyperquadratic continued fractions and automatic sequences
• A short proof of a theorem of Cobham on substitutions
• How to prove that a sequence is not automatic
• Title not available (Why is that?)
• Mixing properties and entropy bounds of a family of Pisot random substitutions
• An asymptotic version of Cobham’s theorem
• Eigenvalues and transduction of morphic sequences
• From combinatorial games to shape-symmetric morphisms
• Quantitative estimates for the size of an intersection of sparse automatic sets
• Consistent systems of linear differential and difference equations
• Syndeticity and independent substitutions
• Sum-free sets generated by the period-\(k\)-folding sequences and some Sturmian sequences
• Hidden automatic sequences
• Substitutive systems and a finitary version of Cobham's theorem
• On multiplicative independent bases for canonical number systems in cyclotomic number fields
• 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
• The formal inverse of the period-doubling sequence
• Proving results about OEIS sequences with \texttt{Walnut}
• A theorem of Cobham for non-primitive substitutions

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)