Generalized Cayley Graphs and Cellular Automata over them

arXiv1212.0027MaRDI QIDQ6237650FDOQ6237650

Pablo Arrighi, Vincent Nesme, Simon Martiel

Publication date: 30 November 2012

Abstract: 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. KEYWORDS: Causal Graph Dynamics, Curtis-Hedlund-Lyndon, Dynamical networks, Boolean networks, Generative networks automata, Graph Automata, Graph rewriting automata, L-systems, parallel graph transformations, Amalgamated graph transformations, Time-varying graphs, Regge calculus, Local, No-signalling, Reversibility.

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80) Dynamical systems in other branches of physics (quantum mechanics, general relativity, laser physics) (37N20) Lattice gravity, Regge calculus and other discrete methods in general relativity and gravitational theory (83C27)

This page was built for publication: Generalized Cayley Graphs and Cellular Automata over them

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6237650)