Vincent Nesme ; Guillaume Theyssier - Selfsimilarity, Simulation and Spacetime Symmetries

dmtcs:2973 - Discrete Mathematics & Theoretical Computer Science, January 1, 2011, DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems - https://doi.org/10.46298/dmtcs.2973
Selfsimilarity, Simulation and Spacetime Symmetries

Authors: Vincent Nesme ; Guillaume Theyssier

    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.


    Volume: DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems
    Section: Proceedings
    Published on: January 1, 2011
    Imported on: January 31, 2017
    Keywords: cellular automata,simulation,reversibility,time symmetry,space symmetry,linear,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS],[NLIN.NLIN-CG] Nonlinear Sciences [physics]/Cellular Automata and Lattice Gases [nlin.CG],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

    Share

    Consultation statistics

    This page has been seen 146 times.
    This article's PDF has been downloaded 149 times.