Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type

摘要

Subshifts of finite type are sets of colorings of the plane defined by local constraints. They can be seen as a discretization of continuous dynamical systems. We investigate here the hardness of deciding factorization, conjugacy and embedding of subshift