Geodesic
Selfsimilarity, Simulation and Spacetime Symmetries
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems, DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems (2011).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2011_special_261_a5,
     author = {Nesme, Vincent and Theyssier, Guillaume},
     title = {Selfsimilarity, {Simulation} and {Spacetime} {Symmetries}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems},
     year = {2011},
     doi = {10.46298/dmtcs.2973},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2973/}
}
TY  - JOUR
AU  - Nesme, Vincent
AU  - Theyssier, Guillaume
TI  - Selfsimilarity, Simulation and Spacetime Symmetries
JO  - Discrete mathematics & theoretical computer science
PY  - 2011
VL  - DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2973/
DO  - 10.46298/dmtcs.2973
LA  - en
ID  - DMTCS_2011_special_261_a5
ER  - 
%0 Journal Article
%A Nesme, Vincent
%A Theyssier, Guillaume
%T Selfsimilarity, Simulation and Spacetime Symmetries
%J Discrete mathematics & theoretical computer science
%D 2011
%V DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2973/
%R 10.46298/dmtcs.2973
%G en
%F DMTCS_2011_special_261_a5
Nesme, Vincent; Theyssier, Guillaume. Selfsimilarity, Simulation and Spacetime Symmetries. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems, DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems (2011). doi : 10.46298/dmtcs.2973. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2973/

Cité par Sources :