No Arabic abstract
Classification is a central problem for dynamical systems, in particular for families that arise in a wide range of topics, like substitution subshifts. It is important to be able to distinguish whether two such subshifts are isomorphic, but the existing invariants are not sufficient for this purpose. We first show that given two minimal substitution subshifts, there exists a computable constant $R$ such that any factor map between these subshifts (if any) is the composition of a factor map with a radius smaller than $R$ and some power of the shift map. Then we prove that it is decidable to check whether a given sliding block code is a factor map between two prescribed minimal substitution subshifts. As a consequence of these two results, we provide an algorithm that, given two minimal substitution subshifts, decides whether one is a factor of the other and, as a straightforward corollary, whether they are isomorphic.
We prove decidability results on the existence of constant subsequences of uniformly recurrent morphic sequences along arithmetic progressions. We use spectral properties of the subshifts they generate to give a first algorithm deciding whether, given p $in$ N, there exists such a constant subsequence along an arithmetic progression of common difference p. In the special case of uniformly recurrent automatic sequences we explicitely describe the sets of such p by means of automata.
Minimal Cantor systems of finite topological rank (that can be represented by a Bratteli-Vershik diagram with a uniformly bounded number of vertices per level) are known to have dynamical rigidity properties. We establish that such systems, when they are expansive, define the same class of systems, up to topological conjugacy, as primitive and recognizable ${mathcal S}$-adic subshifts. This is done establishing necessary and sufficient conditions for a minimal subshift to be of finite topological rank. As an application, we show that minimal subshifts with non-superlinear complexity (like all classical zero entropy examples) have finite topological rank. Conversely, we analyze the complexity of ${mathcal S}$-adic subshifts and provide sufficient conditions for a finite topological rank subshift to have a non-superlinear complexity. This includes minimal Cantor systems given by Bratteli-Vershik representations whose tower levels have proportional heights and the so called left to right ${mathcal S}$-adic subshifts. We also exhibit that finite topological rank does not imply non-superlinear complexity. In the particular case of topological rank 2 subshifts, we prove their complexity is always subquadratic along a subsequence and their automorphism group is trivial.
It has been recently proved that the automorphism group of a minimal subshift with non-superlinear word complexity is virtually $mathbb{Z}$ [DDPM15, CK15]. In this article we extend this result to a broader class proving that the automorphism group of a minimal S-adic subshift of finite alphabet rank is virtually $mathbb{Z}$. The proof is based on a fine combinatorial analysis of the asymptotic classes in this type of subshifts, which we prove are a finite number.
Dimension groups are complete invariants of strong orbit equivalence for minimal Cantor systems. This paper studies a natural family of minimal Cantor systems having a finitely generated dimension group, namely the primitive unimodular proper S-adic subshifts. They are generated by iterating sequences of substitutions. Proper substitutions are such that the images of letters start with a same letter, and similarly end with a same letter. This family includes various classes of subshifts such as Brun subshifts or dendric subshifts, that in turn include Arnoux-Rauzy subshifts and natural coding of interval exchange transformations. We compute their dimension group and investigate the relation between the triviality of the infinitesimal subgroup and rational independence of letter measures. We also introduce the notion of balanced functions and provide a topological characterization of bal-ancedness for primitive unimodular proper S-adic subshifts.
We prove that on B-free subshifts, with B satisfying the Erdos condition, all cellular automata are determined by monotone sliding block codes. In particular, this implies the validity of the Garden of Eden theorem for such systems.