Abstract
Automata networks are finite collections of entities (the automata), each automaton having its own set of possible states, which interact with each other over discrete time, interactions being defined as local functions allowing the automata to change their state according to the states of their neighbourhoods. Inspired by natural phenomena, the studies on this very abstract and expressive model of computation have underlined the very importance of the way (i.e. the schedule) according to which the automata update their states, namely the update modes which can be deterministic, periodic, fair, or not. Indeed, a given network may admit numerous underlying dynamics, these latter depending highly on the update modes under which we let the former evolve. In this paper, we focus on a new kind of deterministic, periodic and fair update mode family introduced recently in a modelling framework, called the block-parallel update modes by duality with the well-known and studied block-sequential update modes. We compare block-parallel to block-sequential update modes, then count them: (1) in absolute terms, (2) by keeping only representatives leading to distinct dynamics, and (3) by keeping only representatives giving rise to non-isomorphic limit dynamics. Put together, this paper constitutes a first theoretical analysis of these update modes and their impact on automata networks dynamics.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aracena, J., Goles, E., Moreira, A., Salinas, L.: On the robustness of update schedules in Boolean networks. Biosystems 97, 1–8 (2009)
Davidich, M.I., Bornholdt, S.: Boolean network model predicts cell cycle sequence of fission yeast. PLoS ONE 3, e1672 (2008)
Demongeot, J., Noual, M., Sené, S.: Combinatorics of Boolean automata circuits dynamics. Disc. Appl. Math. 160(4–5), 398–415 (2012)
Demongeot, J., Sené, S.: About block-parallel Boolean networks: a position paper. Nat. Comput. 19, 5–13 (2020)
Dennunzio, A., Formenti, E., Manzoni, L., Porreca, A.E.: Complexity of the dynamics of reaction systems. Inf. Comput. 267, 96–109 (2019)
Fierz, B., Poirier, M.G.: Biophysics of chromatin dynamics. Ann. Rev. Biophys. 48, 321–345 (2019)
Goles, E., Noual, M.: Block-sequential update schedules and Boolean automata circuits. In: Proceedings of AUTOMATA 2010, pp. 41–50. DMTCS (2010)
Hübner, M.R., Spector, D.L.: Chromatin dynamics. Ann. Rev. Biophys. 39, 471–489 (2010)
Kauffman, S.A.: Metabolic stability and epigenesis in randomly constructed genetic nets. J. Theor. Biol. 22, 437–467 (1969)
Mendoza, L., Alvarez-Buylla, E.R.: Dynamics of the genetic regulatory network for Arabidopsis thaliana flower morphogenesis. J. Theor. Biol. 193, 307–319 (1998)
Noual, M.: Updating automata networks. PhD thesis, École normale supérieure de Lyon (2012)
Paulevé, L., Sené, S.: Systems Biology Modelling and Analysis: Formal Bioinformatics Methods and Tools, Chapter Boolean Networks and their Dynamics: the Impact of Updates, pp. 173–250. Wiley, Hoboken (2022)
Perrot, K., Sené, S., Tapin, L.: On countings and enumerations of block-parallel automata networks. Preprint on arXiv:2304.09664 (2023)
Robert, F.: Discrete iterations: a metric study. Springer Series in Computational Mathematics, vol. 6. Springer, Heidelberg (1986). https://doi.org/10.1007/978-3-642-61607-5
Thomas, R.: Boolean formalization of genetic control circuits. J. Theor. Biol. 42, 563–585 (1973)
Acknowledgments
The authors were funded mainly by their salaries as French State agents.This work has been secondarily supported by ANR-18-CE40-0002 FANs project (KP & SS), ECOS-Sud C19E02 SyDySy project (SS), and STIC AmSud 22-STIC-02 CAMA project (KP, LT & SS), and the MSCA-SE-101131549 ACANCOS (KP, LT & SS).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Perrot, K., Sené, S., Tapin, L. (2024). Combinatorics of Block-Parallel Automata Networks. In: Fernau, H., Gaspers, S., Klasing, R. (eds) SOFSEM 2024: Theory and Practice of Computer Science. SOFSEM 2024. Lecture Notes in Computer Science, vol 14519. Springer, Cham. https://doi.org/10.1007/978-3-031-52113-3_31
Download citation
DOI: https://doi.org/10.1007/978-3-031-52113-3_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-52112-6
Online ISBN: 978-3-031-52113-3
eBook Packages: Computer ScienceComputer Science (R0)