Skip to Main content Skip to Navigation
Conference papers

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

Emmanuel Jeandel 1 Pascal Vanier 2
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
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.
Complete list of metadatas

https://hal.inria.fr/hal-00840384
Contributor : Emmanuel Jeandel <>
Submitted on : Tuesday, July 2, 2013 - 1:52:04 PM
Last modification on : Tuesday, December 18, 2018 - 4:48:02 PM

Identifiers

Collections

Citation

Emmanuel Jeandel, Pascal Vanier. Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type. STACS - 30th International Symposium on Theoretical Aspects of Computer Science, Christian-Albrechts-Universität zu Kiel, Feb 2013, Kiel, Germany. pp.490--501, ⟨10.4230/LIPIcs.STACS.2013.490⟩. ⟨hal-00840384⟩

Share

Metrics

Record views

283