Cellular automata over generalized Cayley graphs

Pablo Arrighi (1) , S. Martiel (2) , V. Nesme

1 CANA - Calcul Naturel
2 School of Physics and Astronomy [Leeds]

Cayley graphs have a number of useful features: the ability to graphically represent finitely generated group elements and their relations ; to name all vertices relative to a point; and the fact that they have a well-defined notion of translation. We propose a notion of graph associated to a language, which conserves or generalizes these features. Whereas Cayley graphs are very regular; associated graphs are arbitrary, although of a bounded degree. Moreover, it is well-known that cellular automata can be characterized as the set of translation-invariant continuous functions for a distance on the set of configurations that makes it a compact metric space; this point of view makes it easy to extend their definition from grids to Cayley graphs. Similarly, we extend their definition to these arbitrary, bounded degree, time-varying graphs. The obtained notion of Cellular Automata over generalized Cayley graphs is stable under composition and under inversion.

Mots clés: Causal Graph Dynamics; Curtis-Hedlund-Lyndon; Dynamical networks; Boolean networks; Generative networks automata; Graph Automata; Graph rewriting automata; Parallel graph transformations; Amalgamated graph transformations; Time-varying graphs; Regge calculus; Local; No-signalling; Reversibility

Domaines: Informatique [cs]

Pablo Arrighi, S. Martiel, V. Nesme. Cellular automata over generalized Cayley graphs. Mathematical Structures in Computer Science, 2018, 18, pp.340-383. ⟨hal-01785458⟩