Cellular automata over generalized Cayley graphs
Open Access
- 29 May 2017
- journal article
- conference paper
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 28 (3) , 340-383
Abstract
It is well-known that cellular automata can be characterized as the set of translation-invariant continuous functions over a compact metric space; this point of view makes it easy to extend their definition from grids to Cayley graphs. 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 an origin; and the fact that they have a well-defined notion of translation. We propose a notion of graphs, which preserves or generalizes these features. Whereas Cayley graphs are very regular, generalized Cayley graphs are arbitrary, although of a bounded degree. We extend cellular automata theory to these arbitrary, bounded degree, time-varying graphs. The obtained notion of cellular automata is stable under composition and under inversion.Keywords
This publication has 30 references indexed in Scilit:
- Intrinsic Universality of Causal Graph DynamicsElectronic Proceedings in Theoretical Computer Science, 2013
- Topological rewriting and the geometrization of programmingPhysica D: Nonlinear Phenomena, 2008
- Graph automata: natural expression of self-reproductionPhysica D: Nonlinear Phenomena, 2002
- Simulations between cellular automata on Cayley graphsTheoretical Computer Science, 1999
- Endomorphisms of symbolic algebraic varietiesJournal of the European Mathematical Society, 1999
- Parallel high-level replacement systemsTheoretical Computer Science, 1997
- Algebraic approach to single-pushout graph transformationTheoretical Computer Science, 1993
- Parallel and distributed derivations in the single-pushout approachTheoretical Computer Science, 1993
- Time-evolution problem in regge calculusPhysical Review D, 1975
- Endomorphisms and automorphisms of the shift dynamical systemTheory of Computing Systems, 1969