Emergence on Decreasing Sandpile Models

Kévin Perrot () and Eric Rémila
Additional contact information
Kévin Perrot: LIF - Laboratoire d'informatique Fondamentale de Marseille - AMU - Aix Marseille Université - ECM - École Centrale de Marseille - CNRS - Centre National de la Recherche Scientifique

Post-Print from HAL

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 (search for similar items in EconPapers)
Date: 2015-08-24
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-01212069v1
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in MFCS 2015 40th International Symposium on Mathematical Foundations of Computer Science, Aug 2015, Milan, Italy

Downloads: (external link)
https://shs.hal.science/halshs-01212069v1/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:halshs-01212069

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().