Selfsimilarity, Simulation and Spacetime Symmetries

Abstract : We study intrinsic simulations between cellular automata and introduce a new necessary condition for a CA to simulate another one. Although expressed for general CA, this condition is targeted towards surjective CA and especially linear ones. Following the approach introduced by the first author in an earlier paper, we develop proof techniques to tell whether some linear CA can simulate another linear CA. Besides rigorous proofs, the necessary condition for the simulation to occur can be heuristically checked via simple observations of typical space-time diagrams generated from finite configurations. As an illustration, we give an example of linear reversible CA which cannot simulate the identity and which is 'time-asymmetric', i.e. which can neither simulate its own inverse, nor the mirror of its own inverse.
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.77-94, 2011, DMTCS Proceedings
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01196140
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 9 septembre 2015 - 11:15:00
Dernière modification le : jeudi 11 janvier 2018 - 06:12:26
Document(s) archivé(s) le : lundi 28 décembre 2015 - 23:01:51

Fichier

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

Identifiants

  • HAL Id : hal-01196140, version 1

Collections

Citation

Vincent Nesme, Guillaume Theyssier. Selfsimilarity, Simulation and Spacetime Symmetries. 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.77-94, 2011, DMTCS Proceedings. 〈hal-01196140〉

Partager

Métriques

Consultations de la notice

180

Téléchargements de fichiers

115