Syndeticity and independent substitutions

DOI10.1016/J.AAM.2008.02.001zbMATH Open1160.68028arXiv0907.4583OpenAlexW2964066418MaRDI QIDQ2377960FDOQ2377960

Authors: Fabien Durand, Michel Rigo 

Publication date: 20 January 2009

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

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.

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

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

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)

Cites Work

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

Cited In (13)

• Substitutions, abstract number systems and the space filling property
• Dynamics of interval maps generated by erasing substitutions
• Mixing properties of erasing interval maps
• Completing a combinatorial proof of the rigidity of Sturmian words generated by morphisms
• Asymptotic properties of free monoid morphisms
• The growth function of \(S\)-recognizable sets
• The simplest erasing substitution
• An asymptotic version of Cobham’s theorem
• Some remarks about stabilizers
• Title not available (Why is that?)
• Rigidity and Substitutive Dendric Words
• 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)