Syndeticity and independent substitutions

DOI10.1016/J.AAM.2008.02.001MaRDI QIDQ2377960zbMATH OpenOpenAlexFDO

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)

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

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)