Pablo Arrighi, Gilles Dowek
We generalize the theory of Cellular Automata to arbitrary, time-varying
graphs. In other words we formalize, and prove theorems about, the intuitive
idea of a labelled graph which evolves in time - but under the natural
constraint that information can only ever be transmitted at a bounded speed,
with respect to the distance given by the graph. The notion of
translation-invariance is also generalized. The definition we provide for these
`causal graph dynamics' is simple and axiomatic. The theorems we provide also
show that it is robust. For instance, causal graph dynamics are stable under
composition and under restriction to radius one. In the finite case some
fundamental facts of Cellular Automata theory carry through: causal graph
dynamics admit a characterization as continuous functions and they are stable
under inversion. The provided examples suggest a wide range of applications of
this mathematical object, from complex systems science to theoretical physics.
Keywords: Dynamical networks, Boolean networks, Generative networks automata,
Cayley cellular automata, Graph Automata, Graph rewriting automata, Parallel
graph transformations, Amalgamated graph transformations, Regge calculus.
View original:
http://arxiv.org/abs/1202.1098
No comments:
Post a Comment