Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Representing Reversi ...
Conference paper

Representing Reversible Cellular Automata with Reversible Block Cellular Automata

Jérôme Durand-Lose ORCID (1)
(1) Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis
Download article
Open on HAL
Imported on
November 21, 2016
Published on
December 31, 2000
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001)
Proceedings
DOI
10.46298/dmtcs.2297
License
https://about.hal.science/hal-authorisation-v1
Indicators
1794
Views
745
Downloads

Representing Reversible Cellular Automata with Reversible Block Cellular Automata

Jérôme Durand-Lose ORCID (1)
(1) Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis
Abstract
Cellular automata are mappings over infinite lattices such that each cell is updated according tothe states around it and a unique local function.Block permutations are mappings that generalize a given permutation of blocks (finite arrays of fixed size) to a given partition of the lattice in blocks.We prove that any d-dimensional reversible cellular automaton can be exp ressed as thecomposition of d+1 block permutations.We built a simulation in linear time of reversible cellular automata by reversible block cellular automata (also known as partitioning CA and CA with the Margolus neighborhood) which is valid for both finite and infinite configurations. This proves a 1990 conjecture by Toffoli and Margolus <i>(Physica D 45)</i> improved by Kari in 1996 <i>(Mathematical System Theory 29)</i>.
Keywords
  • [INFO]Computer Science [cs]
  • [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • Cellular automata
  • reversibility
  • block cellular automata
  • partitioning cellular automata
Cited by

Source: OpenCitations

  • The Ideal Energy of Classical Lattice Dynamics

    arXiv (Cornell University)

    Authors : Norman Margolus

    Journal reference : Volume , 2015, pp. 169-180

    DOI : 10.1007/978-3-662-47221-7_13
  • Surprising Areas in the Quest for Small Universal Devices

    Electronic Notes in Theoretical Computer Science

    Authors : Maurice Margenstern

    Journal reference : Volume 225, 2009, pp. 201-220

    DOI : 10.1016/j.entcs.2008.12.075
  • Computing Inside the Billiard Ball Model

    Authors : Jérôme Durand-Lose ORCID

    Journal reference : Volume , 2002, pp. 135-160

    DOI : 10.1007/978-1-4471-0129-1_6
  • Finite-State Classical Mechanics

    Lecture notes in computer science

    Authors : Norman Margolus

    Journal reference : Volume , 2018, pp. 47-60

    DOI : 10.1007/978-3-319-99498-7_3
  • Computational universality of fungal sandpile automata

    arXiv (Cornell University)

    Authors : Eric Goles, Michail-Antisthenis Tsompanas ORCID, Andrew Adamatzky ORCID, Martin Tegelaar ORCID, Han A.B. Wosten ORCID, Genaro J. Martínez ORCID

    Journal reference : Volume 384, 2020, pp. 126541

    DOI : 10.1016/j.physleta.2020.126541
  • Agent Motion Planning as Block Asynchronous Cellular Automata: Pushing, Pulling, Suplexing, and More

    Lecture notes in computer science

    Authors : Hayashi Ani, Josh Brunner, Erik D. Demaine ORCID, Jenny Diomidova, Timothy Gomez ORCID, Della Hendrickson, Yael Kirkpatrick, Jeffery Li, Jayson Lynch ORCID, Ritam Nag, Frederick Stock

    Journal reference : Volume , 2024, pp. 219-236

    DOI : 10.1007/978-3-031-63742-1_16
  • Theory of cellular automata: A survey

    Theoretical Computer Science

    Authors : Jarkko Kari ORCID

    Journal reference : Volume 334, 2005, pp. 3-33

    DOI : 10.1016/j.tcs.2004.11.021
  • On the Collision-Propagation and Gather-Update Formulations of a Cellular Automata Rule

    Lecture notes in computer science

    Authors : Bastien Chopard ORCID, Jean-Luc Falcone ORCID, Ranaivo Razakanirina, Alfons Hoekstra ORCID, Alfonso Caiazzo ORCID

    Journal reference : Volume , 2008, pp. 144-151

    DOI : 10.1007/978-3-540-79992-4_19
  • The Ideal Energy of Classical Lattice Dynamics

    Emergence, complexity and computation

    Authors : Norman Margolus

    Journal reference : Volume , 2016, pp. 59-71

    DOI : 10.1007/978-3-319-33924-5_3
  • Quantum causal graph dynamics

    arXiv (Cornell University)

    Authors : Pablo Arrighi ORCID, Simon Martiel ORCID

    Journal reference : Volume 96, 2017, pp.

    DOI : 10.1103/physrevd.96.024026
  • Modeling and Processing Using Reversible Conservative Noisy Elementary Cellular Automata Circuits and their M-Ary Quantum Computing

    Intelligent Automation & Soft Computing

    Authors : Anas N. Al-Rabadi

    Journal reference : Volume 14, 2008, pp. 177-206

    DOI : 10.1080/10798587.2008.10642990
  • Simulation and Intrinsic Universality Among Reversible Cellular Automata, the Partition Cellular Automata Leverage

    Emergence, complexity and computation

    Authors : Jérôme Durand-Lose ORCID

    Journal reference : Volume , 2018, pp. 61-93

    DOI : 10.1007/978-3-319-73216-9_4
  • Discrete Physics, Cellular Automata and Cryptography

    Lecture notes in computer science

    Authors : Stephane Marconi, Bastien Chopard ORCID

    Journal reference : Volume , 2006, pp. 617-626

    DOI : 10.1007/11861201_72
  • Causal graph dynamics

    Information and Computation

    Authors : Pablo Arrighi ORCID, Gilles Dowek ORCID

    Journal reference : Volume 223, 2012, pp. 78-93

    DOI : 10.1016/j.ic.2012.10.019
  • Classification of Cellular Automata

    Cellular Automata

    Authors : Klaus Sutner

    Journal reference : Volume , 2009, pp. 185-200

    DOI : 10.1007/978-1-4939-8700-9_50
  • Partial Reversibility of One-Dimensional Cellular Automata

    Authors : Ronaldo de Castro Corrêa, Pedro P. B. de Oliveira ORCID

    Journal reference : Volume , 2016, pp. 120-134

    DOI : 10.1007/978-3-319-39300-1_10
Preview
Loading PDF preview...