Simon Martiel

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 timevarying graphs in two different ways: A first axiomatic definition, as continuous and shiftinvariant 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 ndimensionnal discrete spaces using a correspondance between graphs and ndimensional oriented simplicial complexes. 