Abstract
Modules were introduced as an extension of Boolean automata networks. They have inputs which are used in the computation said modules perform, and can be used to wire modules with each other. In the present paper we extend this new formalism and study the specific case of acyclic modules. These modules prove to be well described in their limit behavior by functions called output functions. We provide other results that offer an upper bound on the number of attractors in an acyclic module when wired recursively into an automata network, alongside a diversity of complexity results around the difficulty of deciding the existence of cycles depending on the number of inputs and the size of said cycle.
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
Alon, N.: Asynchronous threshold networks. Graphs Combin. 1, 305–310 (1985). https://doi.org/10.1007/BF02582959
Aracena, J.: Maximum number of fixed points in regulatory Boolean networks. Bull. Math. Biol. 70, 1398–1409 (2008). https://doi.org/10.1007/s11538-008-9304-7
Aracena, J., Gómez, L., Salinas, L.: Limit cycles and update digraphs in Boolean networks. Discrete Appl. Math. 161, 1–12 (2013)
Aracena, J., Richard, A., Salinas, L.: Number of fixed points and disjoint cycles in monotone Boolean networks. SIAM J. Discrete Math. 31, 1702–1725 (2017)
Bernot, G., Tahi, F.: Behaviour preservation of a biological regulatory network when embedded into a larger network. Fund. Inform. 91, 463–485 (2009)
Biane, C., Delaplace, F.: Causal reasoning on Boolean control networks based on abduction: theory and application to cancer drug discovery. IEEE/ACM Trans. Comput. Biol. Bioinform. 16, 1574–1585 (2019)
Davidich, M.I., Bornholdt, S.: Boolean network model predicts cell cycle sequence of fission yeast. PLoS One 3, e1672 (2008)
Delaplace, F., Klaudel, H., Melliti, T., Sené, S.: Analysis of modular organisation of interaction networks based on asymptotic dynamics. In: Gilbert, D., Heiner, M. (eds.) CMSB 2012. LNCS, pp. 148–165. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33636-2_10
Demongeot, J., Goles, E., Morvan, M., Noual, M., Sené, S.: Attraction basins as gauges of robustness against boundary conditions in biological complex systems. PLoS One 5, e11793 (2010)
Demongeot, J., Noual, M., Sené, S.: Combinatorics of Boolean automata circuits dynamics. Discr. Appl. Math. 160, 398–415 (2012)
Elspas, B.: The theory of autonomous linear sequential networks. IRE Trans. Circuit Theory 6(1), 45–60 (1959)
Feder, T.: Stable networks and product graphs. Ph.D thesis, Stanford Univ. (1990)
Floreen, P., Orponen, P.: Counting stable states and sizes of attraction domains in Hopfield nets is hard. In: Proceedings of the of IJCNN 1989, pp. 395–399 (1989)
Goles, E., Salinas, L.: Comparison between parallel and serial dynamics of Boolean networks. Theor. Comput. Sci. 396, 247–253 (2008)
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., Sené, S.: Synchronism versus asynchronism in monotonic Boolean automata networks. Nat. Comput. 17(2), 393–402 (2017). https://doi.org/10.1007/s11047-016-9608-8
Orponen, P.: Neural networks and complexity theory. In: Havel, I.M., Koubek, V. (eds.) MFCS 1992. LNCS, vol. 629, pp. 50–61. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-55808-X_5
Pardo, J., Ivanov, S., Delaplace, F.: Sequential reprogramming of biological network fate. In: Bortolussi, L., Sanguinetti, G. (eds.) CMSB 2019. LNCS, vol. 11773, pp. 20–41. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-31304-3_2
Perrot, K., Perrotin, P., Sené, S.: A framework for (de)composing with boolean automata networks. In: Durand-Lose, J., Verlan, S. (eds.) MCU 2018. LNCS, vol. 10881, pp. 121–136. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-92402-1_7
Robert, F.: Discrete Iterations: A Metric Study. Springer, Heidelberg (1986). https://doi.org/10.1007/978-3-642-61607-5
Siebert, H.: Dynamical and structural modularity of discrete regulatory networks. In: Proceedings of COMPMOD 2009, volume 6 of EPTCS, pp. 109–124 (2009)
Thomas, R.: Boolean formalization of genetic control circuits. J. Theor. Biol. 42, 563–585 (1973)
Acknowledgments
The works of Kévin Perrot and Sylvain Sené were funded mainly by their salaries as French State agents, affiliated to Aix-Marseille Univ., Univ. de Toulon, CNRS, LIS, UMR 7020, Marseille, France (both) and to Univ. Côte d’Azur, CNRS, I3S, UMR 7271, Sophia Antipolis, France (KP), and secondarily by ANR-18-CE40-0002 FANs project, ECOS-Sud C16E01 project, STIC AmSud CoDANet 19-STIC-03 (Campus France 43478PD) project.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Perrot, K., Perrotin, P., Sené, S. (2020). On the Complexity of Acyclic Modules in Automata Networks. In: Chen, J., Feng, Q., Xu, J. (eds) Theory and Applications of Models of Computation. TAMC 2020. Lecture Notes in Computer Science(), vol 12337. Springer, Cham. https://doi.org/10.1007/978-3-030-59267-7_15
Download citation
DOI: https://doi.org/10.1007/978-3-030-59267-7_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-59266-0
Online ISBN: 978-3-030-59267-7
eBook Packages: Computer ScienceComputer Science (R0)