Sand piles: from physics to cellular automata models
type: Item
instance of: scholarly article
title: Sand piles: from physics to cellular automata models
zbMATH Open document ID: 1251.37017
author: M. Comito
author: D. Bianucci
author: G. Cattaneo
published in: Theoretical Computer Science
publication date: 2012-06-25T00:00:00Z
Mathematics Subject Classification ID: 37B15
Mathematics Subject Classification ID: 94A17
Mathematics Subject Classification ID: 68Q80
zbMATH DE Number: 6049406
zbMATH Keywords: sand piles
zbMATH Keywords: information and thermodynamical entropies
zbMATH Keywords: discrete time dynamical systems
zbMATH Keywords: cellular automata
MaRDI profile type: Publication
full work available at URL: j.tcs.2012.02.034
OpenAlex ID: W2087092792
cites work: Conservation of some dynamical properties for operations on cellular automata
cites work: Disks, Balls, and Walls: Analysis of a Combinatorial Game
cites work: Information Entropy and Granulation Co–Entropy of Partitions and Coverings: A Summary
cites work: Q3425572
cites work: Q5331549
cites work: The lattice of integer partitions
cites work: Q3500008
cites work: Q4799365
cites work: Solution of some conjectures about topological properties of linear cellular automata
cites work: Q4418688
cites work: Mathematical Foundations of Computer Science 2005
cites work: From sandpiles to sand automata
cites work: Sand automata as cellular automata
cites work: On the directional dynamics of additive cellular automata
cites work: Q3507547
cites work: Q3429639
cites work: Games on line graphs and sand piles
cites work: Sandpiles and order structure of integer partitions
cites work: Consistency of the adiabatic theorem
cites work: A Mathematical Theory of Communication
cites work: Balancing vectors in the max norm
DOI: 10.1016/J.TCS.2012.02.034
review text: The article deals with the sand pile model: finitely many piles of finitely many grains are juxtaposed and grains of a pile sequentially fall down to the right-neighboring pile if the latter does not get higher than the former.NEWLINENEWLINEThis system is intrinsically nondeterministic: sometimes several piles are simultaneously in the situation where they can be fired (they have at least 2 grains more than their respective right neighbors), but it is (conjectured in the article, but actually) known (from [\textit{E. Formenti} and \textit{B. Masson}, ``On computing fixed points for generalized sandpiles'', Int. J. Unconv. Comput. 2, 51--72 (2006)]) that all possible evolutions eventually lead to the same equilibrium configuration.NEWLINENEWLINEThe authors here propose several ways to chose between these possible evolution paths. First, one can select the path that maximizes or minimizes locally the (discrete) integral (called associated action) of the Lagrangian, which is basically (a simple affine map of) the potential energy (depending on the height of every grain). Nevertheless, this does not determine a unique path.NEWLINENEWLINEInstead, one can do the same with the (Lagrangian computed from the) information entropy (average uncertainty of the pile distribution seen as an integer partition) instead of the potential energy. This does determine a path uniquely: actually, one for local minimization, called adiabatic evolution, and one for local maximization, called anti-adiabatic evolution. However, these do not coincide with the global maximizing or minimizing paths.NEWLINENEWLINEOne can do the same with thermodynamical entropy (logarithm of the thermodynamics probability) which, again, does not determine unique maximizing or minimizing paths.NEWLINENEWLINEA simple cellular automaton model is also presented, that corresponds to the parallel evolution: each pile that can be fired is fired synchronously. Unfortunately, this evolution may not involve the same interme…
description: scientific article; zbMATH DE number 6049406