Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Reports

Simulations Between Cellular Automata on Cayley Graphs.

Abstract : We consider cellular automata on Cayley graphs and compare their computational powers according to the architecture on which they work. We show that, if there exists a homomorphism with a finite kernel from a group into another one such that the image of the first group has a finite index in the second one, then every cellular automaton on the Cayley graph of one of these groups can be uniformally simulated by a cellular automaton on the Cayley graph of the other one. This simulation can be constructed in a linear time. With the help of this result we also show that cellular automata working on any Archimedean tiling can be simulated by a cellular automaton on the grid of Z^2 and conversely.
Document type :
Reports
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102053
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:12:59 AM
Last modification on : Saturday, September 11, 2021 - 3:19:16 AM

File

RR1994-40.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102053, version 1

Collections

Citation

Zsuzsanna Roka. Simulations Between Cellular Automata on Cayley Graphs.. [Research Report] LIP RR-1994-40, Laboratoire de l'informatique du parallélisme. 1994, 2+29p. ⟨hal-02102053⟩

Share

Metrics

Record views

8

Files downloads

126