2013/04/18 by Kevin Perrot, Eric Rémila
Computer Science · Mathematics · #cs.DM #math.CO
published as Theoretical Computer Science, ISSN 0304-3975, 10.1016/j.tcs.2013.01.033 · 30 pages. arXiv admin note: text overlap with arXiv:1106.2670, arXiv:1101.5940
arxiv created 2013/04/18 · arxiv updated 2013/04/19
Sand pile models are dynamical systems describing the evolution from N stacked grains to a stable configuration. It uses local rules to depict grain moves and iterate it until reaching a fixed configuration from which no rule can be applied. Physicists L. Kadanoff \em et al inspire KSPM, extending the well known \em Sand Pile Model (SPM). In KSPM(D), we start from a pile of N stacked grains and apply the rule: D - 1 grains can fall from column i onto columns i+1,i+2,…,i+D - 1 if the difference of height between columns i and i + 1 is greater or equal to D. Toward the study of fixed points (stable configurations on which no grain can move) obtained from N stacked grains, we propose an iterative study of KSPM evolution consisting in the repeated addition of one grain on a heap of sand, triggering an avalanche at each iteration. We develop a formal background for the study of avalanches, resumed in a finite state word transducer, and explain how this transducer may be used to predict the form of fixed points. Further precise developments provide a plain formula for fixed points of KSPM(3), showing the emergence of a wavy shape.