Hardness of conjugacy and factorization of multidimensional subshifts of finite type
Emmanuel Jeandel, Pascal Vanier · arXiv (Cornell University) · 2012
We investigate here the hardness of conjugacy and factorization of subshifts of finite type (SFTs) in dimension d> 1. In particular, we prove that the factorization problem is Σ03-complete and the conjugacy problem Σ01-complete in the arithmetical hierarchy. Keywords:Subshift of finite type, factorization, conjugacy, arithmetical hierarchy, computability, tilings.