Representing Reversible Cellular Automata with Reversible Block Cellular Automata
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....
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2001-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2297/pdf |
| _version_ | 1797270650889437184 |
|---|---|
| author | Jérôme Durand-Lose |
| author_facet | Jérôme Durand-Lose |
| author_sort | Jérôme Durand-Lose |
| collection | DOAJ |
| description | 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>. |
| first_indexed | 2024-04-25T02:07:39Z |
| format | Article |
| id | doaj.art-bed1d59642594abb88dd59cea45502d4 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:07:39Z |
| publishDate | 2001-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-bed1d59642594abb88dd59cea45502d42024-03-07T14:27:42ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502001-01-01DMTCS Proceedings vol. AA,...Proceedings10.46298/dmtcs.22972297Representing Reversible Cellular Automata with Reversible Block Cellular AutomataJérôme Durand-Lose0https://orcid.org/0000-0001-6506-074XLaboratoire d'Informatique, Signaux, et Systèmes de Sophia AntipolisCellular 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>.https://dmtcs.episciences.org/2297/pdfcellular automatareversibilityblock cellular automatapartitioning cellular automata[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] |
| spellingShingle | Jérôme Durand-Lose Representing Reversible Cellular Automata with Reversible Block Cellular Automata Discrete Mathematics & Theoretical Computer Science cellular automata reversibility block cellular automata partitioning cellular automata [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] |
| title | Representing Reversible Cellular Automata with Reversible Block Cellular Automata |
| title_full | Representing Reversible Cellular Automata with Reversible Block Cellular Automata |
| title_fullStr | Representing Reversible Cellular Automata with Reversible Block Cellular Automata |
| title_full_unstemmed | Representing Reversible Cellular Automata with Reversible Block Cellular Automata |
| title_short | Representing Reversible Cellular Automata with Reversible Block Cellular Automata |
| title_sort | representing reversible cellular automata with reversible block cellular automata |
| topic | cellular automata reversibility block cellular automata partitioning cellular automata [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] |
| url | https://dmtcs.episciences.org/2297/pdf |
| work_keys_str_mv | AT jeromedurandlose representingreversiblecellularautomatawithreversibleblockcellularautomata |