2021/05/14 by Johan Kopra, Ville Salo, Kopra, Johan +1
Computer Science · Mathematics · #Cellular Automata and Applications #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #General Topology (math.GN) #Mathematical Dynamics and Fractals #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2105.06767
openalex publication_date 2021/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Systems obtained by quotienting a subshift of finite type (SFT) by another SFT are called finitely presented in the literature. Analogously, if a sofic shift is quotiented by a sofic equivalence relation, we call the resulting system sofically presented. Generalizing an observation of Fried, for all discrete countable monoids M, we show that M-subshift/SFT systems are precisely the expansive dynamical M-systems, where S1/S2 denotes the class of systems obtained by quotienting subshifts in S1 by (relative) subshifts in S2. We show that for all finitely generated infinite monoids M, M-SFT \subsetneq M-sofic \subsetneq M-SFT/SFT = M-sofic/SFT \subsetneq M-SFT/sofic = M-sofic/sofic, and that Mañé's theorem about the dimension of expansive systems characterizes the virtually cyclic groups. In the case of one-dimensional actions, Mañe's theorem generalizes to sofically presented systems, which also have finite topological dimension. The basis of this is the construction of an explicit metric for a sofically presented system. We show that any finite connected simplicial complex is a connected component of a finitely presented system, and prove that conjugacy of one-dimensional sofically presented dynamical systems is undecidable. A key idea is the introduction of so-called automatic spaces. We also study the automorphism groups and periodic points of sofically presented systems. We also perform two case studies. First, in the context of β-shifts, we define the β-kernel -- the least subshift relation that identifies 1 with its orbit. We give a classification of the β-shift/β-kernel pair as a function of β. Second, we revisit the classical study of toral automorphisms in our framework, and in particular for the classical "golden mean" toral automorphism we explicitly compute the kernel of the standard presentation.