Fiche du document
24 août 2015
- handle: 10670/1.lxlfva
- halshs: halshs-01212069
info:eu-repo/semantics/OpenAccess
Mots-clés
sandpile models fixed points emergence C - Mathematical and Quantitative Methods/C.C7 - Game Theory and Bargaining TheorySujets proches
Quartz sandCiter ce document
Kévin Perrot et al., « Emergence on Decreasing Sandpile Models », HAL-SHS : économie et finance, ID : 10670/1.lxlfva
Métriques
Partage / Export
Résumé
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?