Hardness of conjugacy, embedding and factorization of multidimensional subshifts

作者：

Highlights：

• Knowing whether two SFTs of dimension higher than two are conjugate or if one embeds in the other is Σ10-complete.

• Deciding whether one of two multidimensional SFTs, effective or sofic shifts factor onto the other is Σ30-complete.

• For effective subshifts, all the results are also true in dimension one.

摘要

•Knowing whether two SFTs of dimension higher than two are conjugate or if one embeds in the other is Σ10-complete.•Deciding whether one of two multidimensional SFTs, effective or sofic shifts factor onto the other is Σ30-complete.•For effective subshifts, all the results are also true in dimension one.

论文关键词：Subshifts,Computability,Factorization,Embedding,Conjugacy,Subshift of finite type,Arithmetical Hierarchy,Tilings,SFTs

论文评审过程：Received 23 October 2014, Revised 11 May 2015, Accepted 20 May 2015, Available online 5 June 2015, Version of Record 25 August 2015.

论文官网地址：https://doi.org/10.1016/j.jcss.2015.05.003