Skip to Main content Skip to Navigation

Proprietes combinatoires de certaines familles d'automates cellulaires

Abstract : The study and the understanding of natural phenomena such as earthquakes, and tidal waves have puzzled physicists for a long time. Indeed, it seems that classical models based on continous functions can hardly explain the physical observations. In 1987, Bak, Tang and Wiesenfeld introduce a new model based on a cellular automaton whose experimental study shows behaviours similar to earthquakes'. This automaton is called the Sandpile Automaton. In 1990, Dhar, Ruelle Sen and Verma study the mathematical properties of this automaton. This article gives the basis of an algebraic theory of the critical states of the system, showing that they form a finite abelian group. This thesis focuses on the study of the Sandpile group from an algorithmical, combinatorial and algebraic point of view. At first, we study the complexity of the group operator~; then, we give the structure of the group on several usual families of graphs such as wheels and complete graphs to finally show that the group of a planar graph is isomorph to the group of each of its geometric duals. We also show how to associate a polynomial ideal to an abelian group, and for the sandpile group we give a characterization of the group operator and of the identity in terms of polynomial reductions.
Document type :
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Dominique Rossin Connect in order to contact the contributor
Submitted on : Thursday, January 5, 2006 - 11:01:18 AM
Last modification on : Saturday, November 20, 2021 - 3:49:34 AM
Long-term archiving on: : Saturday, April 3, 2010 - 7:58:44 PM



  • HAL Id : tel-00011297, version 1


Dominique Rossin. Proprietes combinatoires de certaines familles d'automates cellulaires. Combinatorics [math.CO]. Ecole Polytechnique X, 2000. English. ⟨tel-00011297⟩



Record views


Files downloads