2026-08-16T15:58:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3959 2024-03-06T10:34:42Z ddc:004 open_access

Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type Jeandel, Emmanuel Vanier, Pascal Subshifts Computability Factorization Embedding Conjugacy 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emmanuel Jeandel and Pascal Vanier 2013 Is Part Of LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2013.490 urn:nbn:de:0030-drops-39592 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.490 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode