Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type
Résumé
Subshifts of finite type are sets of colorings of the plane defined by local constraints. They can be seen as a discretization of continuous dynamical systems. We investigate here the hardness of deciding factorization, conjugacy and embedding of subshifts of finite type (SFTs) in dimension d > 1. In particular, we prove that the factorization problem is Σ03-complete and that the conjugacy and embedding problems are Σ01-complete in the arithmetical hierarchy.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...