Hardness of conjugacy and factorization of multidimensional subshifts of finite type

Abstract

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 ${\Sigma }_3^0$-complete and the conjugacy problem ${\Sigma }_1^0$-complete in the arithmetical hierarchy.