Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Issue title: From Physics to Computer Science: to Gianpiero Cattaneo for his 70th birthday
Article type: Research Article
Authors: Formenti, Enrico | Goles, Eric | Martin, Bruno
Affiliations: Université Nice–Sophia Antipolis, F-06903 Sophia Antipolis Cedex, France. enrico.formenti@unice.fr | Universidad Adolfo Ibañez, Av. Diagonal Las Torres 2640, Peñalolen, Santiago, Chile. eric.chacc@uai.cl | Université Nice–Sophia Antipolis, F-06903 Sophia Antipolis Cedex, France. Bruno.Martin@i3s.unice.fr
Note: [] Work supported by The French National Research Agency project EMC (ANR-09-BLAN-0164). Address for correspondence: Université Nice–Sophia Antipolis, I3S, UMR 6070 CNRS, 2000 route des Lucioles, BP 121, F-06903 Sophia Antipolis Cedex
Note: [] FONDECYT 1100003, BASAL-CMM-U. de Chile, Anillo ACT-88, CNRS.
Note: [] Work supported by The French National Research Agency project EMC (ANR-09-BLAN-0164).
Abstract: This paper investigates the avalanche problem AP for the Kadanoff sandpile model (KSPM). We prove that (a slight restriction of) AP is in NC1 in dimension one, leaving the general case open. Moreover, we prove that AP is P-complete in dimension two. The proof of this latter result is based on a reduction from the monotone circuit value problem by building logic gates and wires which work with an initial sand distribution in KSPM. These results are also related to the known prediction problem for sandpiles which is in NC1 for one-dimensional sandpiles and P-complete for dimension 3 or higher. The computational complexity of the prediction problem remains open for the Bak's model of two-dimensional sandpiles.
Keywords: Kadanoff Sandpile Model, Bak Sandpile Model, Sandpiles Models, Complexity, Discrete Dynamical Systems, Self-Organized Criticality (SOC)
DOI: 10.3233/FI-2012-643
Journal: Fundamenta Informaticae, vol. 115, no. 1, pp. 107-124, 2012
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
如果您在出版方面需要帮助或有任何建, 件至: editorial@iospress.nl