2011/06/14 by Kévin Perrot, Eric Rémila · 1 citation
Computer Science · #cs.DM
published as MFCS 2011, ARCoSS LNCS Springer-Verlag, volume 6907, pages 508-520 · 14 pages
arxiv created 2011/06/14 · arxiv updated 2013/02/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. The main interest of sand piles relies in their \em Self Organized Criticality (SOC), the property that a small perturbation | adding some sand grains | on a fixed configuration has uncontrolled consequences on the system, involving an arbitrary number of grain fall. Physicists L. Kadanoff \em et al inspire KSPM, a model presenting a sharp SOC behavior, extending the well known \em Sand Pile Model. 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 the D-1 adjacent columns to the right if the difference of height between columns i and i+1 is greater or equal to D. This paper develops a formal background for the study of KSPM fixed points. This background, resumed in a finite state word transducer, is used to provide a plain formula for fixed points of KSPM(3).