<abstract xmlns="http://www.w3.org/1999/xhtml"><p> The Sand Pile Model (SPM) and its generalization, the Ice Pile Model (IPM), originate from physics and have various applications in the description of the evolution of granular systems. In this article, we deal with the enumeration and the exhaustive generation of the accessible configuration of the system. Our work is based on a new recursive decomposition theorem for SPM configurations using the notion of staircase bases. Based on this theorem, we provide a recursive formula for the enumeration of SPM(n) and a constant amortized time (CAT) algorithm for the generation of all SPM(n) configurations. The extension of the same approach to the Ice Pile Model is also discussed. </p></abstract>

The Sand Pile Model (SPM) and its generalization, the Ice Pile Model (IPM), originate from physics and have various applications in the description of the evolution of granular systems. In this article, we deal with the enumeration and the exhaustive generation of the accessible configuration of the system. Our work is based on a new recursive decomposition theorem for SPM configurations using the notion of staircase bases. Based on this theorem, we provide a recursive formula for the enumeration of SPM(n) and a constant amortized time (CAT) algorithm for the generation of all SPM(n) configurations. The extension of the same approach to the Ice Pile Model is also discussed.

A recursive structure of sand pile model and its applications

roberto.mantaci@liafa.univ-paris-diderot.fr

Université Paris Diderot - Paris 7 F-75205 Paris Cedex 13, France

Pure Mathematics and Applications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"A recursive structure of sand pile model and its applications"}

The Sand Pile Model (SPM) and its generalization, the Ice Pile Model (IPM), originate from physics and have various applications in the description of the...

A recursive structure of sand pile model and its applications

Pubblicato online: 07 ott 2015

Pagine: 63 - 78

Ricevuto: 24 mag 2013

DOI: https://doi.org/10.1515/puma-2015-0006

Parole chiave
sand pile, ice pile, CAT algorithm, exhaustive generation, recursive algorithm

© 2015

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

A recursive structure of sand pile model and its applications

Pubblicato online: 07 ott 2015

Pagine: 63 - 78

Ricevuto: 24 mag 2013

DOI: https://doi.org/10.1515/puma-2015-0006

Parole chiavesand pile, ice pile, CAT algorithm, exhaustive generation, recursive algorithm

© 2015

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Parole chiave
sand pile, ice pile, CAT algorithm, exhaustive generation, recursive algorithm