Decidability of the isomorphism and the factorization for minimal substitution subshifts

ABSTRACT
Classification is a central problem in the study of dynamical systems, in particular for families of systems that arise in a wide range of topics. Hence it is important to have algorithms deciding wether a dynamical system have some given property.

Let us mention subshifts of finite type that appear, for example, in information theory, hyperbolic dynamics, $C^*$-algebra, statistical mechanics and thermodynamic formalism. The most important and longstanding open problem for this family originates in [Williams:1973] and is stated in [Boyle:2008] as follows : Classify subshifts of finite type up to topological isomorphism. In particular, give a procedure which decides when two non-negative integer matrices define topologically conjugate subshifts of finite type.

Another well-known family of subshifts, that is also defined through matrices, with a wide range of interests is the family of substitution subshifts. These subshifts are concerned, for example, with automata theory, first order logic, combinatorics on words, quasicrystallography, fractal geometry, group theory and number theory.In this talk we will show that not only the existence of isomorphism between such subshifts is decidable but also the factorization.

Posted on Nov 19, 2018 in Dynamical Systems, Seminars