License: 
Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.490
URN: urn:nbn:de:0030-drops-39592
URL: https://drops.dagstuhl.de/opus/volltexte/2013/3959/
Jeandel, Emmanuel ;
Vanier, Pascal
Hardness of Conjugacy, Embedding and 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 Sigma^0_3-complete and that the conjugacy and embedding problems are Sigma^0_1-complete in the arithmetical hierarchy.
BibTeX - Entry
@InProceedings{jeandel_et_al:LIPIcs:2013:3959,
author = {Emmanuel Jeandel and Pascal Vanier},
title = {{Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type}},
booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
pages = {490--501},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-50-7},
ISSN = {1868-8969},
year = {2013},
volume = {20},
editor = {Natacha Portier and Thomas Wilke},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/3959},
URN = {urn:nbn:de:0030-drops-39592},
doi = {10.4230/LIPIcs.STACS.2013.490},
annote = {Keywords: Subshifts, Computability, Factorization, Embedding, Conjugacy}
}
|
Keywords: |
|
Subshifts, Computability, Factorization, Embedding, Conjugacy |
|
Collection: |
|
30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) |
|
Issue Date: |
|
2013 |
|
Date of publication: |
|
26.02.2013 |
