Simulations Between Cellular Automata on Cayley Graphs. - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1994

Simulations Between Cellular Automata on Cayley Graphs.

(1)
1

Résumé

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.
Nous comparons la puissance de calcul des automates cellulaires agis sant sur dierents graphes de Cayley Nous montrons que s'il existe un morphisme a noyau fini d'un groupe dans un autre tel que l'indice de l'image du premier groupe est ni dans le deuxieme alors tout automate cellulaire sur le graphe de Cayley d'un de ces groupes peut etre simule par un automate cellulaire sur le graphe de Cayley de l'autre groupe avec un facteur de perte de temps lineaire Nous montrons aussi que les automates cellulaires agissant sur les pavages Archimediens peuven tetre simules par un automate cellulaire sur la grille de Z et reciproquement
Fichier principal
Vignette du fichier
RR1994-40.pdf (314.51 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02102053 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102053 , version 1

Citer

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⟩
11 Consultations
139 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More