Syndeticity and independent substitutions

DOI10.1016/J.AAM.2008.02.001MaRDI QIDQ2377960zbMATHOpenAlexFDO

Authors Fabien Durand, Michel Rigo

Publication date 20 January 2009

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

substitutionsCobham's theorempolynomial growth orderabstract numeration systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15) Automata sequences (11B85)

Abstract: We associate in a canonical way a substitution to any abstract numeration system built on a regular language. In relationship with the growth order of the letters, we define the notion of two independent substitutions. Our main result is the following. If a sequence $x$ is generated by two independent substitutions, at least one being of exponential growth, then the factors of $x$ appearing infinitely often in $x$ appear with bounded gaps. As an application, we derive an analogue of Cobham's theorem for two independent substitutions (or abstract numeration systems) one with polynomial growth, the other being exponential.

Recommendations

• Cobham's theorem for substitutions
• Substitutive systems and a finitary version of Cobham's theorem
• A theorem of Cobham for non-primitive substitutions
• A short proof of a theorem of Cobham on substitutions
• A generalization of Cobham's theorem

Cites work

• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 1916667 (Why is no real title available?)
• A theorem of Cobham for non-primitive substitutions
• An Introduction to Symbolic Dynamics and Coding
• Automatic Sequences
• Bertrand numeration systems and recognizability
• Complexité des facteurs des mots infinis engendrés par morphismes itérés
• Independent numeration systems and syndeticity
• Numeration systems on a regular language
• On recognizable sets of integers
• On the base-dependence of sets of numbers recognizable by finite automata
• Substitution dynamical systems - spectral analysis
• Uniform tag sequences

Cited in

(14)

• Asymptotic properties of free monoid morphisms
• Decidability of uniform recurrence of morphic sequences
• Rigidity and substitutive dendric words
• On extended boundary sequences of morphic and Sturmian words
• Some remarks about stabilizers
• Substitutions, abstract number systems and the space filling property
• Mixing properties of erasing interval maps
• The growth function of \(S\)-recognizable sets
• Completing a combinatorial proof of the rigidity of Sturmian words generated by morphisms
• An asymptotic version of Cobham’s theorem
• scientific article; zbMATH DE number 3911728 (Why is no real title available?)
• Dynamics of interval maps generated by erasing substitutions
• Catalan numbers as discrepancies for a family of substitutions on infinite alphabets
• The simplest erasing substitution

This page was built for publication: Syndeticity and independent substitutions

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