Projective subdynamics and universal shifts

Abstract : We study the projective subdynamics of two-dimensional shifts of finite type, which is the set of one-dimensional configurations that appear as columns in them. We prove that a large class of one-dimensional shifts can be obtained as such, namely the effective subshifts which contain positive-entropy sofic subshifts. The proof involves some simple notions of simulation that may be of interest for other constructions. As an example, it allows us to prove the undecidability of all non-trivial properties of projective subdynamics.
Type de document :
Communication dans un congrès
Fatès, Nazim and Goles, Eric and Maass, Alejandro and Rapaport, Iván. 17th International Workshop on Celular Automata and Discrete Complex Systems, 2011, Santiago, Chile. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems, pp.123-134, 2011, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01196136
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 9 septembre 2015 - 11:14:55
Dernière modification le : jeudi 18 janvier 2018 - 01:58:55
Document(s) archivé(s) le : lundi 28 décembre 2015 - 23:08:53

Fichier

dmAP0109.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01196136, version 1

Collections

Citation

Pierre Guillon. Projective subdynamics and universal shifts. Fatès, Nazim and Goles, Eric and Maass, Alejandro and Rapaport, Iván. 17th International Workshop on Celular Automata and Discrete Complex Systems, 2011, Santiago, Chile. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems, pp.123-134, 2011, DMTCS Proceedings. 〈hal-01196136〉

Partager

Métriques

Consultations de la notice

295

Téléchargements de fichiers

165