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

abstract numeration systemsCobham's theorempolynomial growth ordersubstitutions

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 1916667 (Why is no real title available?)
• 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

(15)

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

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)