@inproceedings{b85f059078734806a22471cb43a3c251,
title = "Factorization of multidimensional subshifts of finite type",
abstract = "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 ∑03-complete and that the conjugacy and embedding problems are ∑ 01-complete in the arithmetical hierarchy.",
keywords = "Computability, Conjugacy, Embedding, Factorization, Subshifts",
author = "Emmanuel Jeandel and Pascal Vanier",
year = "2013",
month = dec,
day = "1",
doi = "10.4230/LIPIcs.STACS.2013.490",
language = "English",
isbn = "9783939897507",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
pages = "490--501",
booktitle = "30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013",
note = "30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013 ; Conference date: 27-02-2013 Through 02-03-2013",
}