» Sandpiles
1. Introduction
2. Definitions
2.1 Definitions
2.2 Known results
3. Generalizations
3.1 Initial condition
3.2 Symmetric model
Bibliography
Bibliography
3. Generalizations
The previous results are interesting, buck lack generality. There are two main problems, which we tried to solve in different papers.
- What happens when the initial condition is changed, and does not consists in a configuration with a single column?
- How can we define a similar model which allows grains to fall in several directions (and dimensions)?
3.1 Initial condition
The complete study of SPM and IPM(k) with arbitrary initial conditions can be found in [5] for SPM, and in [6] for IPM(k).
When starting from an arbitrary configuration c, the problème is much more complicated. It becomes impossible to determine the fixed point in constant time, however we wrote a fast algorithm which computes a fixed point in time O(l.min(l,n)). The following theorem proves that we compute the correct fixed point.
Theorem 3 [6]. For all k, for any configuration c, the orbit graph of c for IPM(k) is a finite lattice.
Roughly, the algorithm cuts the configuration into small parts which are easier to analyse, merges them as soon as possible and loops until it can not merge anymore, according to the following structure.
Fixed point computation algorithm for generalized sandpiles.
For more details, please refer to [5, 6].
3.2 Symmetric model
We also looked for a symmetric (falling at the same time on the left and on the right) model of sandpiles, to get a more realistic model than SPM. The main problem is that all intuitive definitions of such a model lead to orbit graphs which are not lattices. We bypassed this issue by defining in [7] a model whose orbit graph has a simple structure, although it is not a lattice.
The model SSPM (Symmetric Sand Pile Model [7]) is defined by two concurrent vertical rules. One moves the grains towards the right, the other towards the left, both can be applied when the difference between the heights of the two neighboring columns is greater than 2:
Vertical rules of SSPM.
There was already non-determinism in SPM because we did not know where to apply the rule, now appears the fact that a different rule can be applied at the same place. For example, we have the following orbit graph when starting from the configuration (5) in IPM(3).
Orbit graph of (5) for SSPM.
Although this graph is not a lattice, it is possible to characterize its elements (see [7] for the details), so we could identify and count the fixed points. The result is amazingly simple:
Proposition 4 [7]. For all n, the orbit graph of (n) for SSPM has ⌊√n⌋ fixed points.
Bibliography
| [1] | P. Bak, C. Tang, et K. Wiesenfeld. Self-organized criticality. Physical Review A, 38(1):364−374, 1988. |
| [2] | E. Goles and M. A. Kiwi. Games on line graphs and sand piles. Theoretical Computer Science, 115(2):321−349, 1993. |
| [3] | E. Goles, M. Morvan, and H. D. Phan. Sand piles and order structure of integer partitions. Discrete Applied Mathematics, 117:51−64, 2002. |
| [4] | T. Brylawski. The lattice of integer partitions. Discrete mathematics, 6:201−219, 1973. |
| [5] | E. Formenti and B. Masson. On Computing Fixed Points for Generalized Sandpiles. International Journal of Unconventional Computing, 2(1):13−25, Old City Publishing, 2006. |
| [6] | E. Formenti and B. Masson. A note on fixed points of generalized ice pile models. International Journal of Unconventional Computing, 2(2), Old City Publishing, 2006. |
| [7] | E. Formenti, B. Masson and T. Pisokas. On symmetric sandpiles. In Cellular Automata for Research and Industry (ACRI 2006), Lecture Notes in Computer Sciences, Springer-Verlag, 2006. |