Emergence on Decreasing Sandpile Models

Perrot Kevin 1 Éric Rémila 2
1 LIF - Laboratoire d'informatique Fondamentale de Marseille
2 GATE Lyon Saint-Étienne - Groupe d'analyse et de théorie économique
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 : sandpile models fixed points emergence
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

Collections

GATE-TCM | GATE | UNIV-LYON1 | ENS-LYON | UNIV-ST-ETIENNE | EC-MARSEILLE | TDS-MACS | LIF | UNIV-AMU | LIS-LAB

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〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

279

Téléchargements de fichiers

28

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD