# 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 :
Type de document :
Communication dans un congrès
MFCS 2015 40th International Symposium on Mathematical Foundations of Computer Science, Aug 2015, Milan, Italy. MFCS 2015 40th International Symposium on Mathematical Foundations of Computer Science, 2015
Domaine :
Liste complète des métadonnées

Littérature citée [17 références]

https://halshs.archives-ouvertes.fr/halshs-01212069
Contributeur : Soledad Beudon <>
Soumis le : vendredi 23 mars 2018 - 12:43:32
Dernière modification le : mercredi 31 octobre 2018 - 12:24:13
Document(s) archivé(s) le : jeudi 13 septembre 2018 - 10:17:26

### Fichier

PerrotRemila-DecresingSandpile...
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : halshs-01212069, version 1

### Citation

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

### Métriques

Consultations de la notice

## 279

Téléchargements de fichiers