LIPIcs.STACS.2013.490.pdf
- Filesize: 0.71 MB
- 12 pages
Document
Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type
Authors
-
Part of:
Volume:
30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2013-02-26
Cite As Get BibTex
Emmanuel Jeandel and Pascal Vanier. Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 490-501, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
https://doi.org/10.4230/LIPIcs.STACS.2013.490
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 Sigma^0_3-complete and that the conjugacy and embedding problems are Sigma^0_1-complete in the arithmetical hierarchy.
Subject Classification
Keywords
- Subshifts
- Computability
- Factorization
- Embedding
- Conjugacy
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads