{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T01:31:25Z","timestamp":1768095085229,"version":"3.49.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"University of Virginia Strategic Investment Fund","award":["SIF160, CMMI-1745207 (EAGER), OAC-1916805 (CINES), CCF-1918656 (Expeditions) and IIS-1908530"],"award-info":[{"award-number":["SIF160, CMMI-1745207 (EAGER), OAC-1916805 (CINES), CCF-1918656 (Expeditions) and IIS-1908530"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>\n            Discrete dynamical systems serve as useful formal models to study diffusion phenomena in social networks. Several recent articles have studied the algorithmic and complexity aspects of some decision problems on synchronous Boolean networks, which are discrete dynamical systems whose underlying graphs are directed, and may contain directed cycles. Such problems can be regarded as reachability problems in the phase space of the corresponding dynamical system. Previous work has shown that some of these decision problems become efficiently solvable for systems on directed acyclic graphs (DAGs). Motivated by this line of work, we investigate a number of decision problems for dynamical systems whose underlying graphs are DAGs. We show that computational intractability (i.e.,\n            <jats:bold>PSPACE<\/jats:bold>\n            -completeness) results for reachability problems hold even for dynamical systems on DAGs. We also identify some restricted versions of dynamical systems on DAGs for which reachability problem can be solved efficiently. In addition, we show that a decision problem (namely, Convergence), which is efficiently solvable for dynamical systems on DAGs, becomes\n            <jats:bold>PSPACE<\/jats:bold>\n            -complete for Quasi-DAGs (i.e., graphs that become DAGs by the removal of a\n            <jats:italic>single<\/jats:italic>\n            edge). In the process of establishing the above results, we also develop several structural properties of the phase spaces of dynamical systems on DAGs.\n          <\/jats:p>","DOI":"10.1145\/3653723","type":"journal-article","created":{"date-parts":[[2024,3,22]],"date-time":"2024-03-22T12:00:53Z","timestamp":1711108853000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7044-0197","authenticated-orcid":false,"given":"Daniel J.","family":"Rosenkrantz","sequence":"first","affiliation":[{"name":"University of Virginia, Charlottesville, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1653-0658","authenticated-orcid":false,"given":"Madhav V.","family":"Marathe","sequence":"additional","affiliation":[{"name":"University of Virginia, Charlottesville, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0893-4364","authenticated-orcid":false,"given":"S.S.","family":"Ravi","sequence":"additional","affiliation":[{"name":"University of Virginia, Charlottesville, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5058-1999","authenticated-orcid":false,"given":"Richard E.","family":"Stearns","sequence":"additional","affiliation":[{"name":"University of Virginia, Charlottesville, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,10]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s12572-018-0237-6"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtbi.2006.09.023"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1093\/ije\/dyy260"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/3304415.3304424"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.02.027"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.026"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.006"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90037-8"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1006\/game.1998.0699"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/3306127.3331774"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/124"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054191000054"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i05.6197"},{"key":"e_1_3_3_15_2","article-title":"Inferring Coupling of Distributed Dynamical Systems via Transfer Entropy","author":"Cliff O. M.","year":"2020","unstructured":"O. M. Cliff, M. Prokopenko, and R. Fitch. 2020. Inferring Coupling of Distributed Dynamical Systems via Transfer Entropy. ArXiv Report: 1611.00549v1.","journal-title":"ArXiv Report: 1611.00549v1"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-20614-6_6"},{"key":"e_1_3_3_17_2","volume-title":"Introduction to Algorithms (Second ed.)","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. 2009. Introduction to Algorithms (Second ed.). MIT Press and McGraw-Hill, Cambridge, MA."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/1205873"},{"key":"e_1_3_3_19_2","first-page":"2185","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Creager E.","year":"2020","unstructured":"E. Creager, D. Madras, T. Pitassi, and R. Zemel. 2020. Causal modeling for fairness in dynamical systems. In Proceedings of the International Conference on Machine Learning(PMLR), San Francisco, CA, 2185\u20132195."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.24"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2014.02.002"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511761942"},{"issue":"6","key":"e_1_3_3_23_2","first-page":"577","article-title":"On the computational complexity of analyzing Hopfield nets","volume":"3","author":"Flor\u00e9en P.","year":"1989","unstructured":"P. Flor\u00e9en and P. Orponen. 1989. On the computational complexity of analyzing Hopfield nets. Complex Systems 3, 6 (1989), 577\u2013587.","journal-title":"Complex Systems"},{"key":"e_1_3_3_24_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman & Co., San Francisco."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1086\/226707"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.2307\/j.ctvcm4gh1"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2036429100"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1142\/9789812770998_0018"},{"key":"e_1_3_3_29_2","first-page":"26","volume-title":"Proceedings of the Workshop on Multi-Agent Interaction Networks (MAIN 2013), held in conjunction with the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), (Minneapolis, MN, May 2013)","author":"Kuhlman C. J.","year":"2013","unstructured":"C. J. Kuhlman, A. Kumar, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, and R. E. Stearns. 2013. Analysis problems for special classes of bi-threshold dynamical systems. In Proceedings of the Workshop on Multi-Agent Interaction Networks (MAIN 2013), held in conjunction with the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), (Minneapolis, MN, May 2013). IFAAMAS, Online publisher, 26\u201333."},{"key":"e_1_3_3_30_2","volume-title":"Biologically Relevant Classes of Boolean Functions","author":"Layne L.","year":"2011","unstructured":"L. Layne. 2011. Biologically Relevant Classes of Boolean Functions. Ph. D. Dissertation. Department of Mathematics, Clemson University."},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2013.6580562"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.5555\/1201984"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.07.008"},{"key":"e_1_3_3_34_2","first-page":"76:1\u201376:13","volume-title":"Proceedings of the 45th MFCS","author":"Ogihara M.","year":"2020","unstructured":"M. Ogihara and K. Uchizawa. 2020. Synchronous Boolean finite dynamical systems on directed graphs over XOR functions. In Proceedings of the 45th MFCS. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Online publisher, 76:1\u201376:13."},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-56939-1_74"},{"issue":"1","key":"e_1_3_3_36_2","first-page":"94","article-title":"Neural networks and complexity theory","volume":"1","author":"Orponen P.","year":"1994","unstructured":"P. Orponen. 1994. Neural networks and complexity theory. Nord. J. Comput. 1, 1 (1994), 94\u2013110.","journal-title":"Nord. J. Comput."},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00058680"},{"key":"e_1_3_3_38_2","first-page":"1585","volume-title":"Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2018) (Stockholm, Sweden, July 10\u201315, 2018)","author":"Rosenkrantz D. J.","year":"2018","unstructured":"D. J. Rosenkrantz, M. V. Marathe, S. S. Ravi, and R. E. Stearns. 2018. Testing phase space properties of synchronous dynamical systems with nested canalyzing local functions. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2018) (Stockholm, Sweden, July 10\u201315, 2018). IFAAMAS, Online publisher, 1585\u20131594."},{"key":"e_1_3_3_39_2","first-page":"11334","volume-title":"Proceedings of the 35th AAAI Conference (AAAI \u201921)","author":"Rosenkrantz D. J.","year":"2021","unstructured":"D. J. Rosenkrantz, M. V. Marathe, S. S. Ravi, and R. E. Stearns. 2021. Synchronous dynamical systems on directed acyclic graphs (DAGs): Complexity and algorithms. In Proceedings of the 35th AAAI Conference (AAAI \u201921). AAAI Press, Online publisher, 11334\u201311342."},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.05.014"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3653723","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3653723","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:58Z","timestamp":1750291438000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3653723"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3653723"],"URL":"https:\/\/doi.org\/10.1145\/3653723","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2023-02-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}