Hardness of conjugacy, embedding and factorization of multidimensional subshifts ?
Knowing whether two SFTs of dimension higher than two are conjugate or if one embeds in the other is ? 1 0 -complete. Deciding whether one of two multidimensional SFTs, effective or sofic shifts factor onto the other is ? 3 0 -complete. For effective subshifts, all the results are also true in dimension one.
conjugacy embedding factorization subshifts sfts computability subshift of finite type arithmetical hierarchy tilings