Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type

Authors Emmanuel Jeandel, Pascal Vanier



PDF
Thumbnail PDF

File

LIPIcs.STACS.2013.490.pdf
  • Filesize: 0.71 MB
  • 12 pages

Document Identifiers

Author Details

Emmanuel Jeandel
Pascal Vanier

Cite AsGet 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.
Keywords
  • Subshifts
  • Computability
  • Factorization
  • Embedding
  • Conjugacy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail