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 metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102053
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:12:59 AM
Last modification on : Wednesday, November 20, 2019 - 2:51:56 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

16

Files downloads

42