Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01196140
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, September 9, 2015 - 11:15:00 AM
Last modification on : Wednesday, February 27, 2019 - 11:08:02 AM
Document(s) archivé(s) le : Monday, December 28, 2015 - 11:01:51 PM

File

dmAP0106.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01196140, version 1

Collections

Citation

Vincent Nesme, Guillaume Theyssier. Selfsimilarity, Simulation and Spacetime Symmetries. 17th International Workshop on Celular Automata and Discrete Complex Systems, 2011, Santiago, Chile. pp.77-94. ⟨hal-01196140⟩

Share

Metrics

Record views

266

Files downloads

526