Abstract
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 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 et al inspire KSPM, a model presenting a sharp SOC behavior, extending the well known 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).
Partially supported by IXXI (Complex System Institute, Lyon) and ANR projects Subtile and MODMAD.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bak, P., Tang, C., Wiesenfeld, K.: Self-organized criticality. Phys. Rev. A 38(1), 364–374 (1988)
Berstel, J., Boasson, L.: Transductions and context-free languages. Teubner (Ed.), pp. 1–278 (1979)
Dartois, A., Magnien, C.: Results and conjectures on the sandpile identity on a lattice. In: Morvan, M., Rémila, É. (eds.) Discrete Models for Complex Systems, DMCS 2003. DMTCS Proceedings, vol. AB, pp. 89–102. Discrete Mathematics and Theoretical Computer Science (2003)
Durand-Lose, J.O.: Parallel transient time of one-dimensional sand pile. Theor. Comput. Sci. 205(1-2), 183–193 (1998)
Formenti, E., Masson, B., Pisokas, T.: Advances in symmetric sandpiles. Fundam. Inform. 76(1-2), 91–112 (2007)
Gajardo, A., Moreira, A., Goles, E.: Complexity of langton’s ant. Discrete Applied Mathematics 117(1-3), 41–50 (2002)
Gale, D., Propp, J., Sutherland, S., Troubetzkoy, S.: Further travels with my ant. Mathematical Entertainments column, Mathematical Intelligencer 17, 48–56 (1995)
Goles, E., Kiwi, M.A.: Games on line graphs and sand piles. Theor. Comput. Sci. 115(2), 321–349 (1993)
Goles, E., Martin, B.: Computational Complexity of Avalanches in the Kadanoff Two-dimensional Sandpile Model. In: TUCS (ed.) Proceedings of JAC 2010 Journées Automates Cellulaires 2010, Turku Finland, pp. 121–132 (December 2010); F.1.1
Goles, E., Morvan, M., Phan, H.D.: The structure of a linear chip firing game and related models. Theor. Comput. Sci. 270(1-2), 827–841 (2002)
Kadanoff, L.P., Nagel, S.R., Wu, L., Zhou, S.-m.: Scaling and universality in avalanches. Phys. Rev. A 39(12), 6524–6537 (1989)
Levine, L., Peres, Y.: Spherical asymptotics for the rotor-router model in z d. Indiana Univ. Math. J, 431–450 (2008)
Moore, C., Nilsson, M.: The computational complexity of sandpiles. Journal of Statistical Physics 96, 205–224 (1999); 10.1023/A:1004524500416
Perrot, K., Rémila, E.: Avalanche structure in the kadanoff sand pile model. In: Dediu, A.-H., Inenaga, S., Martín-Vide, C. (eds.) LATA 2011. LNCS, vol. 6638, pp. 427–439. Springer, Heidelberg (2011), http://arxiv.org/abs/1101.5940
Perrot, K., Rémila, É.: Transduction on Kadanoff Sand Pile Model Avalanches. Application to Wave Pattern Emergence (2011), http://arxiv.org/abs/1106.2670
Phan, T.H.D.: Two sided sand piles model and unimodal sequences. ITA 42(3), 631–646 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag GmbH Berlin Heidelberg
About this paper
Cite this paper
Perrot, K., Rémila, E. (2011). Transduction on Kadanoff Sand Pile Model Avalanches, Application to Wave Pattern Emergence. In: Murlak, F., Sankowski, P. (eds) Mathematical Foundations of Computer Science 2011. MFCS 2011. Lecture Notes in Computer Science, vol 6907. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22993-0_46
Download citation
DOI: https://doi.org/10.1007/978-3-642-22993-0_46
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22992-3
Online ISBN: 978-3-642-22993-0
eBook Packages: Computer ScienceComputer Science (R0)