Hardness of conjugacy and factorization of multidimensional subshifts of   finite type
  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^0_3$-complete and the conjugacy problem $\Sigma^0_1$-complete in the arithmetical hierarchy. 
Jeandel Emmanuel (LIRMM), Pascal Vanier (LIF)
cs.DM