 |
Archive ouverte en Sciences de l'Homme et de la Société |
Conference papers
Emergence on Decreasing Sandpile Models
Abstract : Sand is a proper instance for the study of natural algorithmic phenomena. Idealized square/cubic sand grains moving according to ``simple'' local toppling rules may exhibit surprisingly ``complex'' global behaviors. In this paper we explore the language made by words corresponding to fixed points reached by iterating a toppling rule starting from a finite stack of sand grains in one dimension. Using arguments from linear algebra, we give a constructive proof that for all decreasing sandpile rules the language of fixed points is accepted by a finite (Muller) automaton. The analysis is completed with a combinatorial study of cases where the {\em emergence} of precise regular patterns is formally proven. It extends earlier works, and asks how far can we understand and explain emergence following this track?
Cited literature [17 references]
https://halshs.archives-ouvertes.fr/halshs-01212069
Contributor : Soledad Beudon <>
Submitted on : Friday, March 23, 2018 - 12:43:32 PM
Last modification on : Thursday, April 30, 2020 - 3:12:06 PM
Long-term archiving on: : Thursday, September 13, 2018 - 10:17:26 AM
Contributor : Soledad Beudon <>
Submitted on : Friday, March 23, 2018 - 12:43:32 PM
Last modification on : Thursday, April 30, 2020 - 3:12:06 PM
Long-term archiving on: : Thursday, September 13, 2018 - 10:17:26 AM
File
PerrotRemila-DecresingSandpile...
Files produced by the author(s)