Generalized Cayley Graphs and Cellular Automata over them
From MaRDI portal
Small world graphs, complex networks (graph-theoretic aspects) (05C82) Dynamical aspects of cellular automata (37B15) Dynamical systems in other branches of physics (quantum mechanics, general relativity, laser physics) (37N20) Cellular automata (computational aspects) (68Q80) Lattice gravity, Regge calculus and other discrete methods in general relativity and gravitational theory (83C27) Deterministic network models in operations research (90B10)
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.
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)
