How Hard is it to Predict Sandpiles on Lattices? A Survey

• Autorzy: Formenti Enrico , Perrot Kévin

Identyfikatory

DOI

10.3233/FI-2020-1879

• Języki publikacji: EN

Abstrakty

EN

Since their introduction in the 80s, sandpile models have raised interest for their simple definition and their surprising dynamical properties. In this survey we focus on the computational complexity of the prediction problem, namely, the complexity of knowing, given a finite configuration c and a cell x in c, if cell x will eventually become unstable. This is an attempt to formalize the intuitive notion of “behavioral complexity” that one easily observes in simulations. However, despite many efforts and nice results, the original question remains open: how hard is it to predict the two-dimensional sandpile model of Bak, Tang and Wiesenfeld?

Słowa kluczowe

EN

two-dimensional model; computational complexity; open-ended questions

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 171, nr 1-4
• Strony: 189--219
• Opis fizyczny: Bibliogr. 62 poz., rys.

Twórcy

autor

Formenti Enrico

• Université Côte d'Azur, CNRS, I3S, France

autor

Perrot Kévin

• Aix-Marseille Univ., Toulon Univ., CNRS, LIS, Marseille, France

Bibliografia

• [1] Langton CG. Computation at the edge of chaos: Phase transitions and emergent computation. Physica D: Nonlinear Phenomena, 1990. 42(1):12-37. URL https://doi.org/10.1016/0167-2789(90)90064-V.
• [2] Griffeath D, Moore C. Life Without Death is P-complete. Complex Systems, 1996. 10.
• [3] Machta J, Greenlaw R. The computational complexity of generating random fractals. Journal of Statistical Physics, 1996. 82(5):1299-1326. doi:10.1007/BF02183384.
• [4] Machta J, Moriarty K. The computational complexity of the Lorentz lattice gas. Journal of Statistical Physics, 1997. 87(5):1245-1252. doi:10.1007/BF02181282.
• [5] Matcha J. The computational complexity of pattern formation. Journal of Statistical Physics, 1993. 70(3):949-966. doi:10.1007/BF01053602.
• [6] Moore C, Nordahl MG. Predicting lattice gases is P-complete. Technical report, Santa Fe Institute Working Paper 97-04-034, 1997.
• [7] Neary T, Woods D. P-completeness of Cellular Automaton Rule 110. In: Proceedings of ICALP’2016: Automata, Languages and Programming. 2006 pp. 132-143. doi:10.1007/11786986_13.
• [8] Dennunzio A, Lena PD, Formenti E, Margara L. Periodic Orbits and Dynamical Complexity in Cellular Automata. Fundam. Inform., 2013. 126(2-3):183-199. doi:10.3233/FI-2013-877. URL https://doi.org/10.3233/FI-2013-877.
• [9] Dennunzio A, Formenti E, Manzoni L, Mauri G, Porreca AE. Computational complexity of finite asynchronous cellular automata. Theoretical Computer Science, 2017. 664:131-143. doi:10.1016/j.tcs.2015.12.003.
• [10] Dennunzio A, Guillon P, Masson B. Stable Dynamics of Sand Automata. In: Fifth IFIP International Conference On Theoretical Computer Science - TCS 2008, IFIP 20th World Computer Congress, TC 1, Foundations of Computer Science, September 7-10, 2008, Milano, Italy, volume 273 of IFIP. Springer, 2008 pp. 157-169. doi:10.1007/978-0-387-09680-3_11.
• [11] Acerbi L, Dennunzio A, Formenti E. Shifting and Lifting of Cellular Automata. In: Computation and Logic in the Real World, Third Conference on Computability in Europe, CiE 2007, Siena, Italy, June 18-23, 2007, Proceedings, volume 4497 of Lecture Notes in Computer Science. Springer, 2007 pp. 1-10. doi:10.1007/978-3-540-73001-9_1.
• [12] Dennunzio A. From One-dimensional to Two-dimensional Cellular Automata. Fundam. Inform., 2012. 115(1):87-105. doi:10.3233/FI-2012-642.
• [13] Cattaneo G, Dennunzio A, Formenti E, Provillard J. Non-uniform Cellular Automata. In: Dediu A, Ionescu A, Martín-Vide C (eds.), Language and Automata Theory and Applications, Third International Conference, LATA 2009, Tarragona, Spain, April 2-8, 2009. Proceedings, volume 5457 of Lecture Notes in Computer Science. Springer, 2009 pp. 302-313. doi:10.1007/978-3-642-00982-2_26.
• [14] Cattaneo G, Chiaselotti G, Dennunzio A, Formenti E, Manzoni L. Non Uniform Cellular Automata Description of Signed Partition Versions of Ice and Sand Pile Models. In: Was J, Sirakoulis GC, Bandini S (eds.), Cellular Automata - 11th International Conference on Cellular Automata for Research and Industry, ACRI 2014, Krakow, Poland, September 22-25, 2014. Proceedings, volume 8751 of Lecture Notes in Computer Science. Springer. ISBN 978-3-319-11519-1, 2014 pp. 115-124. doi:10.1007/978-3-319-11520-7_13.
• [15] Dennunzio A, Formenti E, Provillard J. Local rule distributions, language complexity and non-uniform cellular automata. Theor. Comput. Sci., 2013. 504:38-51. doi:10.1016/j.tcs.2012.05.013.
• [16] Bak P, Tang C, Wiesenfeld K. Self-organized criticality: An explanation of the 1/f noise. Physical Review Letters, 1987. 59:381-384. doi:10.1103/PhysRevLett.59.381.
• [17] Bak P, Tang C, Wiesenfeld K. Self-organized criticality. Physical Review A, 1988. 38(1):364-374. doi:10.1103/PhysRevA.38.364.
• [18] Dhar D. Self-organized critical state of sandpile automaton models. Physical Review Letters, 1990. 64:1613-1616. doi: 10.1103/PhysRevLett.64.1613.
• [19] Goles E, Margenstern M. Sand Pile as a universal computer. International Journal of Modern Physics C, 1996. 7(2):113-122. doi:10.1142/S0129183196000120.
• [20] Moore C, Nilsson M. The Computational Complexity of Sandpiles. Journal of Statistical Physics, 1999. 96:205-224. 10.1023/A:1004524500416.
• [21] Goles E, Margenstern M. Universality of the Chip-Firing Game. Theoretical Computer Science, 1997. 172(1-2):121-134. doi:10.1016/S0304-3975(95)00242-1.
• [22] Moore C. Majority-Vote Cellular Automata, Ising Dynamics, and P-Completeness. Journal of Statistical Physics, 1997. 88(3):795-805. doi:10.1023/B:JOSS.0000015172.31951.7b.
• [23] Goles E, Maldonado D, Montealegre P, Ollinger N. On the Computational Complexity of the Freezing Non-strict Majority Automata. In: Proceedings of AUTOMATA’2017. 2017 pp. 109-119.
• [24] Goles E, Montealegre P. Computational complexity of threshold automata networks under different updating schemes. Theoretical Computer Science, 2014. 559:3-19. URL https://doi.org/10.1016/j.tcs.2014.09.010.
• [25] Goles E, Montealegre P. A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton. In: Proceedings of ACRI’2016. 2016 pp. 166-175. doi:10.1007/978-3-319-44365-2_16.
• [26] Goles E, Montealegre P, Perrot K, Theyssier G. On the complexity of two-dimensional signed majority cellular automata. Journal of Computer and System Sciences, 2017. 91:1-32. URL https://doi.org/10.1016/j.jcss.2017.07.010.
• [27] Goles E, Montealegre-Barba P, Todinca I. The complexity of the bootstraping percolation and other problems. Theoretical Computer Science, 2013. 504:73-82. URL https://doi.org/10.1016/j.tcs.2012.08.001.
• [28] Jájá J. An introduction to parallel algorithms. Addison-Wesley, 1992. ISBN 0-201-54856-9.
• [29] Björner A, Lovász L, Shor PW. Chip-firing games on graphs. European Journal of Combinatorics, 1991. 12(4):283-291.
• [30] Bjrner A, Lovász L. Chip-Firing Games on Directed Graphs. Journal of Algebraic Combinatorics, 1992. 1:305-328.
• [31] Formenti E, Masson B, Pisokas T. On Symmetric Sandpiles. In: Proceedings of ACRI’2006, volume 4173 of LNCS. Springer, 2006 pp. 676-685. doi:10.1007/11861201_78.
• [32] Formenti E, Masson B, Pisokas T. Advances in Symmetric Sandpiles. Fundamenta Informaticae, 2007. 76(1-2):91-112.
• [33] Dhar D, Ruelle P, Sen S, Verma DN. Algebraic aspects of abelian sandpile models. Journal of Physics A: Mathematical and General, 1995. 28(4):805.
• [34] Dhar D. The abelian sandpile and related models. Physica A: Statistical Mechanics and its Applications, 1999. 263(1-4):4-25. URL https://doi.org/10.1016/S0378-4371(98)00493-2.
• [35] Levine L, Pegden W, Smart CK. Apollonian structure in the Abelian sandpile. Geometric and Functional Analysis, 2016. 26(1):306-336. doi:10.1007/s00039-016-0358-7.
• [36] Levine L, Pegden W, Smart CK. The Apollonian structure of integer superharmonic matrices. Annals of Mathematics, 2017. 186(1):1-67. doi:10.4007/annals.2017.186.1.1.
• [37] Levine L, Peres Y. Laplacian growth, sandpiles, and scaling limits. Bulletin of the American Mathematical Society, 2017. 54(3):355-382. doi:10.1090/bull/1573.
• [38] Perrot K. Les piles de sable Kadanoff. Ph.D. thesis, École normale supérieure de Lyon, 2013. URL https://tel.archives-ouvertes.fr/tel-00856838.
• [39] Greenlaw R, Hoover HJ, Ruzzo WL. Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, Inc., 1995. ISBN 0-19-508591-4.
• [40] Sipser M. Introduction to the Theory of Computation. Cengage Learning, third edition, 2012. ISBN 978-1133187790.
• [41] Furst M, Saxe JB, Sipser M. Parity, circuits, and the polynomial-time hierarchy. Mathematical systems theory, 1984. 17(1):13-27.
• [42] Håstad J. Computational Limitations of Small-depth Circuits. MIT Press, 1987.
• [43] Dymond PW, Cook SA. Complexity theory of parallel time and hardware. Information and Computation, 1989. 80 (3): 205-226.
• [44] Yang H. An NC algorithm for the general planar monotone circuit value problem. In: Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing. 1991 pp. 196-203. doi:10.1109/SPDP.1991.218279.
• [45] Banks ER. Information processing and transmission in cellular automata. Ph.D. thesis, Massachusetts Institute of Technology, 1971.
• [46] Tardos G. Polynomial bound for a chip firing game on graphs. SIAM Journal of Discrete Mathematics, 1988. 1(3):397-398. doi:10.1137/0401039.
• [47] Miltersen PB. The Computational Complexity of One-dimensional Sandpiles. In: Proceedings of CiE’2005. 2005 pp. 342-348. doi:10.1007/1149464542:
• [48] Formenti E, Goles E, Martin B. Computational Complexity of Avalanches in the Kadanoff Sandpile Model. Fundamenta Informaticae, 2012. 115(1):107-124. doi:10.3233/FI-2012-643.
• [49] Formenti E, Perrot K, Rémila E. Computational complexity of the avalanche problem on one dimensional Kadanoff sandpiles. In: Proceedings of AUTOMATA’2014, volume 8996 of LNCS. 2014 pp. 21-30. doi:10.1007/978-3-319-18812-6_2.
• [50] Formenti E, Perrot K, Rémila E. Computational complexity of the avalanche problem for one dimensional decreasing sandpiles. Journal of Cellular Automata, 2018. 13:215-228.
• [51] Bitar J, Goles E. Parallel chip firing games on graphs. Theoretical Computer Science, 1992. 92(2):291-300. doi:10.1016/0304-3975(92)90316-8.
• [52] McColl WF. Planar Crossovers. IEEE Transactions on Computers, 1981. C-30(3):223-225. doi:10.1109/TC.1981.1675758.
• [53] Regan KW, Vollmer H. Gap-languages and log-time complexity classes. Theoretical Computer Science, 1997. 188 (1): 101-116. doi:10.1016/S0304-3975(96)00288-5.
• [54] Gajardo A, Goles E. Crossing information in two-dimensional Sandpiles. Theoretical Computer Science, 2006. 369(1-3):463-469. doi:10.1016/j.tcs.2006.09.022.
• [55] Delorme M, Mazoyer J. Signals on Cellular Automata. In: Adamatzky A (ed.), Collision-based Computing, pp. 231-275. Springer-Verlag. ISBN 978-1-4471-0129-1, 2002.
• [56] Nguyen VH, Perrot K. Any shape can ultimately cross information on two-dimensional abelian sandpile models. In: Proceedings of AUTOMATA’2018, volume 10875 of LNCS. 2018 pp. 127-142. doi:10.1007/978-3-319-92675-9_10.
• [57] Buss SR. The Boolean Formula Value Problem is in ALOGTIME. In: Proceedings of STOC ’1987. 1987 pp. 123-131.
• [58] Cairns H. Some Halting Problems for Abelian Sandpiles Are Undecidable in Dimension Three. SIAM Journal on Discrete Mathematics, 2018. 32(4):2636-2666. doi:10.1137/16M1091964.
• [59] Cervelle J, Formenti E. On Sand Automata. In: Proceedings of STACS’2003, volume 2607 of LNCS. Springer, 2003 pp. 642-653. doi:10.1007/3-540-36494-3_56.
• [60] Dennunzio A, Guillon P, Masson B. Sand automata as cellular automata. Theoretical Computer Science, 2009. 410(38-40):3962-3974. doi:10.1016/j.tcs.2009.06.016.
• [61] Cervelle J, Formenti E, Masson B. Basic Properties for Sand Automata. In: Proceedings of MFCS’2005, volume 3618 of LNCS. Springer, 2005 pp. 192-211. doi:10.1007/11549345_18.
• [62] Cervelle J, Formenti E, Masson B. From sandpiles to sand automata. Theoretical Computer Science, 2007. 381(1-3):1-28. doi:10.1016/j.tcs.2007.03.042.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).