Recognizability for sequences of morphisms
Preprint
Abstract
We investigate different notions of recognizability for a free monoid morphism $\sigma: \mathcal{A}^* \to \mathcal{B}^*$. Full recognizability occurs when each (aperiodic) point in $\mathcal{B}^\mathbb{Z}$ admits at most one tiling with words $\sigma(a)$, $a \in \mathcal{A}$. This is stronger than the classical notion of recognizability of a substitution $\sigma: \mathcal{A}^*\to\mathcal{A}^*$, where the tiling must be compatible with the language of the substitution. We show that if $|\mathcal A|=2$, or if $\sigma$'s incidence matrix has rank $|\mathcal A|$, or if $\sigma$ is permutative, then $\sigma$ is fully recognizable. Next we investigate the classical notion of recognizability and improve earlier results of Moss\'{e} (1992) and Bezuglyi, Kwiatkowski and Medynets (2009), by showing that any substitution is recognizable for aperiodic points in its substitutive shift. Finally we define recognizability and also eventual recognizability for sequences of morphisms which define an $S$-adic shift. We prove that a sequence of morphisms on alphabets of bounded size, such that compositions of consecutive morphisms are growing on all letters, is eventually recognizable for aperiodic points. We provide examples of eventually recognizable, but not recognizable, sequences of morphisms, and sequences of morphisms which are not eventually recognizable. As an application, for a recognizable sequence of morphisms, we obtain an almost everywhere bijective correspondence between the $S$-adic shift it generates, and the measurable Bratteli-Vershik dynamical system that it defines.
Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Characterization of circular D0L-systemsTheoretical Computer Science, 2019
- Bratteli diagrams where random orders are imperfectProceedings of the American Mathematical Society, 2016
- Finiteness and recognizability problems for substitution maps on two symbolsSemigroup Forum, 2010
- NONSTATIONARY MIXING AND THE UNIQUE ERGODICITY OF ADIC TRANSFORMATIONSStochastics and Dynamics, 2009
- Aperiodic substitution systems and their Bratteli diagramsErgodic Theory and Dynamical Systems, 2009
- The cohomological equation for Roth-type interval exchange mapsJournal of the American Mathematical Society, 2005
- Conjugacies for Tiling Dynamical SystemsCommunications in Mathematical Physics, 2004
- Nonperiodicity implies unique composition for self-similar translationally finite TilingsDiscrete & Computational Geometry, 1998
- A theorem on the Markov periodic approximation in ergodic theoryJournal of Mathematical Sciences, 1985
- Minimal flows arising from substitutions of non-constant lengthTheory of Computing Systems, 1973