Hardness of conjugacy and factorization of multidimensional subshifts of finite type
classification
💻 cs.DM
keywords
conjugacyfactorizationcompletefinitehardnessproblemsigmasubshifts
read the original 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^0_3$-complete and the conjugacy problem $\Sigma^0_1$-complete in the arithmetical hierarchy.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.