Affiliations: EURISE, Univ. Jean Monnet, 23, rue Michelon, 42023 ST
ETIENNE, France | LIP, ENS-Lyon, CNRS UMR 5668, 46 Allée d'Italie,
69364 Lyon Cedex 07, France | Grima, IUT Roanne, Université J. Monnet St-Etienne,
20 avenue de Paris, 42334 Roanne Cedex, France
Abstract: We state a definition of the simulation of graph automata, which are
machines built by putting copies of the same finite-state automaton at the
vertices of a regular graph, reading the states of the neighbors. We first
present the notion of simulation and link it to intrinsic graph properties.
Afterwards, we present some results of simulation between such graph automata,
comparing them to the cellular automata on Cayley graphs. The graphs considered
here are planar, with the elementary cycles of the same length, and form
regular tilings of the hyperbolic plane. We conclude with a possible speed
hierarchy.
