Hardness of conjugacy and factorization of multidimensional subshifts of finite type

Autor:	Emmanuel, Jeandel, Vanier, Pascal
Rok vydání:	2012
Předmět:	Computer Science - Discrete Mathematics
Druh dokumentu:	Working Paper
Popis:	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.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1204.4988 Zobrazit plný text záznamu View this record from Arxiv