# 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?
Keywords :
Document type :
Conference papers
Domain :
Complete list of metadatas

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 : Tuesday, November 19, 2019 - 11:07:06 AM
Long-term archiving on : Thursday, September 13, 2018 - 10:17:26 AM

### File

PerrotRemila-DecresingSandpile...
Files produced by the author(s)

### Identifiers

• HAL Id : halshs-01212069, version 1

### Citation

Kévin Perrot, Éric Rémila. Emergence on Decreasing Sandpile Models. MFCS 2015 40th International Symposium on Mathematical Foundations of Computer Science, Aug 2015, Milan, Italy. ⟨halshs-01212069⟩

Record views