文章基本信息

标题：Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type
本地全文：下载
作者：Emmanuel Jeandel ; Pascal Vanier
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2013
卷号：20
页码：490-501
DOI：10.4230/LIPIcs.STACS.2013.490
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 of finite type (SFTs) in dimension d > 1. In particular, we prove that the factorization problem is Sigma^0_3-complete and that the conjugacy and embedding problems are Sigma^0_1-complete in the arithmetical hierarchy.
关键词：Subshifts; Computability; Factorization; Embedding; Conjugacy