Observations on Abelian sandpile models for directed graphs

We relate various characterizations of sandpile dynamics arising in the literature referred to as "Abelian sandpile models", and we rigorously establish the sense in which they are commutative and associative as algebraic structures. In particular, associativity is approached from different perspectives: directly for the addition of configurations followed by stabilization; as a property of homomorphic images of semigroups; via the composition of operators on configurations; and, more generally, from an asynchronous perspective. We show how the existing formulations all arise within a common framework as substructures or homomorphic images of a non-commutative semigroup of operators. The appendix gives results on the algebraic complexity of sandpile semigroups, with 1) two different proofs determining the Krohn–Rhodes complexity of the finite Abelian sandpile models and all finite Abelian semigroups, 2) exact values of the aperiodic complexity measure for directed non-Abelian sandpile semigroups, and 3) exhibits new kinds of non-Abelian sandpile semigroups of higher Krohn–Rhodes complexity.