Access Restriction

Author Kevin, Perrot ♦ Rémila, Éric
Source Hyper Articles en Ligne (HAL)
Content type Text
File Format PDF
Language English
Subject Keyword sandpile models ♦ fixed points ♦ emergence ♦ shs ♦ info ♦ Humanities and Social Sciences/Economies and finances ♦ Computer Science [cs]/Discrete Mathematics [cs.DM]
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?
Educational Use Research
Learning Resource Type Proceeding
Publisher Date 2015-01-01