Name
Abstract | ||
|---|---|---|
Sand is a proper instance for the study of natural algorithmic phenomena. Idealized square/cubic sand grains moving according to "simple" local toppling rules may exhibit surprisingly "complex" global behaviors. In this paper we explore the language made by words corresponding to fixed points reached by iterating a toppling rule starting from a finite stack of sand grains in one dimension. Using arguments from linear algebra, we give a constructive proof that for all decreasing sandpile rules the language of fixed points is accepted by a finite (Muller) automaton. The analysis is completed with a combinatorial study of cases where the emergence of precise regular patterns is formally proven. It extends earlier works presented in [15-17], and asks how far can we understand and explain emergence following this track? |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-662-48057-1_33 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Sandpile models,Fixed points,Emergence | Discrete mathematics,Linear algebra,Combinatorics,Constructive proof,Computer science,Automaton,Game theory,Fixed point | Conference |
Volume | ISSN | Citations |
9234 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 5 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kévin Perrot | 1 | 13 | 8.36 |
| Eric Rémila | 2 | 329 | 45.22 |