Simon Martiel
(University of Nice-Sophia Antipolis)
Causal Dynamics of Discrete Space

Cellular Automata have always been considered as good toy models for physics and have been studied intensively as such. Eventhough being direct implementation of physics symmetries, these objects still fail to represent some other properties or phenomena in physics. In particular, some physic theories require the possibility of modifying the topology of space in time. A lot of generalizations of this model exist in the litterature but none of them address this question of time varying topology.

In this talk, we will show how to build a cellular automata over time-varying graphs in two different ways: A first axiomatic definition, as continuous and shift-invariant graph transformation, is given. Then a constructive definition is presented, where the graph transformation is induced by a local rule applied simultaneously on every vertex. In a second time, we will show how we can restrict this definition in order to define cellular automata over n-dimensionnal discrete spaces using a correspondance between graphs and n-dimensional oriented simplicial complexes.