2026-07-25T02:54:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19897 2024-05-31T08:33:44Z ddc:004 open_access

Complexity of Boolean Automata Networks Under Block-Parallel Update Modes Perrot, Kévin Sené, Sylvain Tapin, Léah Boolean networks finite dynamical systems block-parallel update schedule Boolean automata networks (aka Boolean networks) are space-time discrete dynamical systems, studied as a model of computation and as a representative model of natural phenomena. A collection of simple entities (the automata) update their 0-1 states according to local rules. The dynamics of the network is highly sensitive to update modes, i.e., to the schedule according to which the automata apply their local rule. A new family of update modes appeared recently, called block-parallel, which is dual to the well studied block-sequential. Although basic, it embeds the rich feature of update repetitions among a temporal updating period, allowing for atypical asymptotic behaviors. In this paper, we prove that it is able to breed complex computations, squashing almost all decision problems on the dynamics to the traditionally highest (for reachability questions) class PSPACE. Despite obtaining these complexity bounds for a broad set of local and global properties, we also highlight a surprising gap: bijectivity is still coNP. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kévin Perrot and Sylvain Sené and Léah Tapin 2024 Is Part Of LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2024.19 urn:nbn:de:0030-drops-198973 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.19 eng https://creativecommons.org/licenses/by/4.0/legalcode