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?
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
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

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〉

Partager

Métriques

Consultations de la notice

249

Téléchargements de fichiers

23