کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429515 | 687592 | 2015 | 17 صفحه PDF | دانلود رایگان |
• 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 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 subshifts in dimensions d>1d>1 for subshifts of finite type and sofic shifts and in dimensions d≥1d≥1 for effective shifts. In particular, we prove that the conjugacy, factorization and embedding problems are Σ30-complete for sofic and effective subshifts and that they are Σ10-complete for SFTs, except for factorization which is also Σ30-complete.
Journal: Journal of Computer and System Sciences - Volume 81, Issue 8, December 2015, Pages 1648–1664