2018/06/13 by Fabien Durand, Durand, Fabien, Julien Leroy +1 · 1 citation
Computer Science · #37B10 #68R15 #Algorithms and Data Compression #Cellular Automata and Applications #Discrete Mathematics (cs.DM) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1806.04891
openalex publication_date 2018/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.