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.
Type de document :
Communication dans un congrès
Natacha Portier and Thomas Wilke. STACS - 30th International Symposium on Theoretical Aspects of Computer Science, Feb 2013, Kiel, Germany. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 20, pp.490--501, 2013, Leibniz International Proceedings in Informatics (LIPIcs). 〈10.4230/LIPIcs.STACS.2013.490〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00840384
Contributeur : Emmanuel Jeandel <>
Soumis le : mardi 2 juillet 2013 - 13:52:04
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25

Identifiants

Citation

Emmanuel Jeandel, Pascal Vanier. Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type. Natacha Portier and Thomas Wilke. STACS - 30th International Symposium on Theoretical Aspects of Computer Science, Feb 2013, Kiel, Germany. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 20, pp.490--501, 2013, Leibniz International Proceedings in Informatics (LIPIcs). 〈10.4230/LIPIcs.STACS.2013.490〉. 〈hal-00840384〉

Partager

Métriques

Consultations de la notice

183