Evènement pour le groupe Séminaire du LaBRI

Date 2012-11-15  13:30-14:30
TitreCausal graph dynamics 
RésuméWe extend 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 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. This is a joint work with Pablo Arrighi  
LieuAmphi du LaBRI 
OrateurGilles Dowek 
UrlDeducteam, INRIA-Rocquencourt 

Aucun document lié à cet événement.

Retour à l'index