On the parameterized complexity of freezing dynamics. (English) Zbl 07844847
Summary: In this paper we establish how alphabet size, treewidth and maximum degree of the underlying graph are key parameters which influence the overall computational complexity of finite freezing automata networks. First, we define a general decision problem, called Specification Checking Problem, that captures many classical decision problems such as prediction, nilpotency, predecessor, asynchronous reachability.
Then, we present a fast-parallel algorithm that solves the general model checking problem when the three parameters are bounded, hence showing that the problem is in NC. Moreover, we show that the problem is in XP on the parameters tree-width and maximum degree.
Finally, we show that these problems are hard from two different perspectives. First, the general problem is W[2]-hard when taking either treewidth or alphabet as single parameter and fixing the others. Second, the classical problems are hard in their respective classes when restricted to families of graph with sufficiently large treewidth.
Then, we present a fast-parallel algorithm that solves the general model checking problem when the three parameters are bounded, hence showing that the problem is in NC. Moreover, we show that the problem is in XP on the parameters tree-width and maximum degree.
Finally, we show that these problems are hard from two different perspectives. First, the general problem is W[2]-hard when taking either treewidth or alphabet as single parameter and fixing the others. Second, the classical problems are hard in their respective classes when restricted to families of graph with sufficiently large treewidth.
MSC:
| 68R99 | Discrete mathematics in relation to computer science |
Keywords:
freezing automata networks; treewidth; fast parallel algorithms; prediction problem; nilpotency problem; asynchronous reachability; predecessor problemReferences:
| [1] | Adrien, Richard, Nilpotent dynamics on signed interaction graphs and weak converses of Thomas’ rules, Discrete Appl. Math., 267, 160-175, Aug 2019 · Zbl 1419.05100 |
| [2] | Amini, Hamed; Fountoulakis, Nikolaos, Bootstrap percolation in power-law random graphs, J. Stat. Phys., 155, 1, 72-92, Feb 2014 · Zbl 1291.82052 |
| [3] | Arnborg, Stefan; Corneil, Derek G.; Proskurowski, Andrzej, Complexity of finding embeddings in a k-tree, SIAM J. Algebraic Discrete Methods, 8, 2, 277-284, April 1987 · Zbl 0611.05022 |
| [4] | Arora, Sanjeev; Barak, Boaz, Computational Complexity: a Modern Approach, 2009, Cambridge University Press · Zbl 1193.68112 |
| [5] | Bak, Per; Chen, Kan; Tang, Chao, A forest-fire model and some thoughts on turbulence, Phys. Lett. A, 147, 5, 297-300, 1990 |
| [6] | Balogh, József; Bollobás, Béla, Bootstrap percolation on the hypercube, Probab. Theory Relat. Fields, 134, 4, 624-648, Jul 2005 · Zbl 1087.60068 |
| [7] | Balogh, József; Bollobás, Béla; Duminil-Copin, Hugo; Morris, Robert, The sharp threshold for bootstrap percolation in all dimensions, Trans. Am. Math. Soc., 364, 5, 2667-2701, may 2012 · Zbl 1238.60108 |
| [8] | Becker, Florent; Maldonado, Diego; Ollinger, Nicolas; Theyssier, Guillaume, Universality in freezing cellular automata, (Sailing Routes in the World of Computation - 14th Conference on Computability in Europe. Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Kiel, Germany, July 30 - August 3, 2018, Proceedings, 2018), 50-59 · Zbl 1509.37018 |
| [9] | Bodlaender, Hans L.; Hagerup, Torben, Parallel algorithms with optimal speedup for bounded treewidth, SIAM J. Comput., 27, 6, 1725-1746, December 1998 · Zbl 0907.68089 |
| [10] | Buss, S. R., The Boolean formula value problem is in ALOGTIME, (Proceedings of the Nineteenth Annual ACM Conference on Theory of Computing - STOC ’87, 1987, ACM Press) |
| [11] | Calamoneri, T., The l(h,k)-labelling problem: a survey and annotated bibliography, Comput. J., 49, 5, 585-608, February 2006 |
| [12] | Carton, Olivier; Guillon, Bruno; Reiter, Fabian, Counter machines and distributed automata, (Cellular Automata and Discrete Complex Systems, 2018, Springer International Publishing), 13-28 · Zbl 1508.68233 |
| [13] | Chekuri, Chandra; Chuzhoy, Julia, Polynomial bounds for the grid-minor theorem, J. ACM, 63, 5, 1-65, Dec 2016 · Zbl 1410.05186 |
| [14] | Cook, Stephen A., The complexity of theorem-proving procedures, (Proceedings of the Third Annual ACM Symposium on Theory of Computing. Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC ’71, 1971, ACM: ACM New York, NY, USA), 151-158 · Zbl 0253.68020 |
| [15] | Courcelle, Bruno, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inf. Comput., 85, 1, 12-75, mar 1990 · Zbl 0722.03008 |
| [16] | Dalmau, Víctor; Kolaitis, Phokion G.; Vardi, Moshe Y., Constraint satisfaction, bounded treewidth, and finite-variable logics, (International Conference on Principles and Practice of Constraint Programming, 2002, Springer), 310-326 · Zbl 1535.68111 |
| [17] | Dennunzio, Alberto; Formenti, Enrico; Manzoni, Luca; Mauri, Giancarlo; Porreca, Antonio E., Computational complexity of finite asynchronous cellular automata, Theor. Comput. Sci., 664, 131-143, February 2017 · Zbl 1359.68207 |
| [18] | Downey, Rod G.; Fellows, Michael R., Fixed-parameter tractability and completeness i: basic results, SIAM J. Comput., 24, 4, 873-921, Aug 1995 · Zbl 0830.68063 |
| [19] | Downey, Rodney G.; Fellows, Michael R., Fundamentals of Parameterized Complexity, 2013, Springer: Springer London · Zbl 1358.68006 |
| [20] | Elberfeld, Michael; Jakoby, Andreas; Tantau, Till, Logspace versions of the theorems of Bodlaender and Courcelle, (2010 IEEE 51st Annual Symposium on Foundations of Computer Science, October 2010, IEEE) |
| [21] | Eric Goles, Diego Maldonado, Pedro Montealegre, Martín Ríos-Wilson, on the complexity of asynchronous freezing cellular automata, 2019. |
| [22] | Fuentes, M. A.; Kuperman, M. N., Cellular automata and epidemiological models with spatial dependence, Phys. A, Stat. Mech. Appl., 267, 3-4, 471-486, 1999 |
| [23] | Gadouleau, Maximilien; Richard, Adrien, Simple dynamics on graphs, Theor. Comput. Sci., 628, 62-77, may 2016 · Zbl 1372.37083 |
| [24] | Gardner, M., The fantastic combinations of John Conway’s new solitaire game “life”, Sci. Am., 223, 120-123, October 1970 |
| [25] | Goldberg, Andrew; Plotkin, Serge; Shannon, Gregory, Parallel symmetry-breaking in sparse graphs, (Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, 1987), 315-324 |
| [26] | Goles, E.; Ollinger, N.; Theyssier, G., Introducing freezing cellular automata, (Exploratory Papers of Cellular Automata and Discrete Complex Systems (AUTOMATA 2015), 2015), 65-73 |
| [27] | Goles, Eric; Maldonado, Diego; Montealegre, Pedro; Ollinger, Nicolas, On the computational complexity of the freezing non-strict majority automata, (Cellular Automata and Discrete Complex Systems - 23rd IFIP WG 1.5 International. Cellular Automata and Discrete Complex Systems - 23rd IFIP WG 1.5 International, Workshop, AUTOMATA 2017, Milan, Italy, June 7-9, 2017, Proceedings, 2017), 109-119 · Zbl 1451.68147 |
| [28] | Goles, Eric; Maldonado, Diego; Montealegre-Barba, Pedro; Ollinger, Nicolas, Fast-parallel algorithms for freezing totalistic asynchronous cellular automata, (Cellular Automata - 13th International Conference on Cellular Automata for Research and Industry, Proceedings. Cellular Automata - 13th International Conference on Cellular Automata for Research and Industry, Proceedings, ACRI 2018, Como, Italy, September 17-21, 2018. Cellular Automata - 13th International Conference on Cellular Automata for Research and Industry, Proceedings. Cellular Automata - 13th International Conference on Cellular Automata for Research and Industry, Proceedings, ACRI 2018, Como, Italy, September 17-21, 2018, Lecture Notes in Computer Science, vol. 11115, 2018, Springer), 406-415 · Zbl 1515.68192 |
| [29] | Goles, Eric; Montealegre-Barba, Pedro; Todinca, Ioan, The complexity of the bootstraping percolation and other problems, Theor. Comput. Sci., 504, 73-82, sep 2013 · Zbl 1297.68092 |
| [30] | Gravner, Janko; Griffeath, David, Cellular automaton growth on z2: theorems, examples, and problems, Adv. Appl. Math., 21, 2, 241-304, 1998 · Zbl 0919.68090 |
| [31] | Green, Frederic, NP-complete problems in cellular automata, Complex Syst., 1, Article 01 pp., 1987 · Zbl 0648.68067 |
| [32] | Greenlaw, Raymond; Hoover, H. James; Ruzzo, Walter L., Limits to Parallel Computation: P-Completeness Theory, 1995, Oxford University Press on Demand · Zbl 0829.68068 |
| [33] | Griffeath, D.; Moore, C., Life without death is P-complete, Complex Syst., 10, 1996 · Zbl 0912.68140 |
| [34] | Holroyd, Alexander E., Sharp metastability threshold for two-dimensional bootstrap percolation, Probab. Theory Relat. Fields, 125, 2, 195-224, 2003 · Zbl 1042.60065 |
| [35] | JáJá, Joseph, An Introduction to Parallel Algorithms, 1992, Addison Wesley Longman Publishing Co., Inc.: Addison Wesley Longman Publishing Co., Inc. USA · Zbl 0781.68009 |
| [36] | Kari, J., The nilpotency problem of one-dimensional cellular automata, SIAM J. Comput., 21, 571-586, 1992 · Zbl 0761.68067 |
| [37] | Kawachi, Akinori; Ogihara, Mitsunori; Uchizawa, Kei, Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs, Theor. Comput. Sci., 762, 25-40, March 2019 · Zbl 1434.68315 |
| [38] | Kermack, William Ogilvy; McKendrick, A. G., A contribution to the mathematical theory of epidemics, Proc. R. Soc. Lond. Ser. A, Contain. Pap. Math. Phys. Character, 115, 772, 700-721, Aug 1927 · JFM 53.0517.01 |
| [39] | Knop, D.; Koutecký, M.; Masařík, T.; Toufar, T., Simplified algorithmic metatheorems beyond mso: treewidth and neighborhood diversity, Log. Methods Comput. Sci., 15, 4, 1860-5974, 2019 · Zbl 1427.68125 |
| [40] | Kreutzer, Stephan; Tazari, Siamak, On brambles, grid-like minors, and parameterized intractability of monadic second-order logic, (Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010,Austin, Texas, USA, January 17-19, 2010, 2010, SIAM), 354-364 · Zbl 1288.05282 |
| [41] | Kutrib, Martin; Malcher, Andreas, Cellular automata with sparse communication, Theor. Comput. Sci., 411, 38-39, 3516-3526, 2010 · Zbl 1207.68214 |
| [42] | Marx, Dániel, Can you beat treewidth?, (48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), 2007, IEEE), 169-179 |
| [43] | Ollinger, Nicolas; Theyssier, Guillaume, Freezing, bounded-change and convergent cellular automata, 2019, CoRR |
| [44] | Omer, Reingold, Undirected connectivity in log-space, J. ACM, 55, 4, 1-24, September 2008 · Zbl 1315.68156 |
| [45] | Robertson, Neil; Seymour, P. D., Graph minors. v. excluding a planar graph, J. Comb. Theory, Ser. B, 41, 1, 92-114, Aug 1986 · Zbl 0598.05055 |
| [46] | Samer, Marko; Szeider, Stefan, Constraint satisfaction with bounded treewidth revisited, J. Comput. Syst. Sci., 76, 2, 103-114, 2010 · Zbl 1186.68443 |
| [47] | Toffoli, Tommaso; Margolus, Norman, Cellular Automata Machines: a New Environment for Modeling, 1987, MIT Press |
| [48] | Ulam, S. M., On some mathematical problems connected with patterns of growth of figures, (Bukrs, A. W., Essays on Cellular Automata, 1970, U. of Illinois Press), 219-231 · Zbl 0241.94048 |
| [49] | Vollmar, R., On cellular automata with a finite number of state changes, (Parallel Processes and Related Automata. Parallel Processes and Related Automata, Computing Supplementum, vol. 3, 1981, Springer: Springer Vienna), 181-191 · Zbl 0458.68013 |
| [50] | Winslow, Andrew, A brief tour of theoretical tile self-assembly, (Cellular Automata and Discrete Complex Systems - 22nd IFIP WG 1.5 International Workshop, Proceedings. Cellular Automata and Discrete Complex Systems - 22nd IFIP WG 1.5 International Workshop, Proceedings, AUTOMATA 2016, Zurich, Switzerland, June 15-17, 2016, 2016), 26-31 · Zbl 1350.68116 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
