DROPS

Document

DOI: 10.4230/LIPIcs.SAND.2024.19

Complexity of Boolean Automata Networks Under Block-Parallel Update Modes

Authors: Kévin Perrot, Sylvain Sené, and Léah Tapin

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract

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.

Cite as

Kévin Perrot, Sylvain Sené, and Léah Tapin. Complexity of Boolean Automata Networks Under Block-Parallel Update Modes. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{perrot_et_al:LIPIcs.SAND.2024.19,
  author =	{Perrot, K\'{e}vin and Sen\'{e}, Sylvain and Tapin, L\'{e}ah},
  title =	{{Complexity of Boolean Automata Networks Under Block-Parallel Update Modes}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.19},
  URN =		{urn:nbn:de:0030-drops-198973},
  doi =		{10.4230/LIPIcs.SAND.2024.19},
  annote =	{Keywords: Boolean networks, finite dynamical systems, block-parallel update schedule}
}

Search Results

Documents authored by Tapin, Léah

Complexity of Boolean Automata Networks Under Block-Parallel Update Modes

Abstract

Cite as

Thanks for your feedback!

Could not send message