Document Open Access Logo

Dynamical Properties of Disjunctive Boolean Networks (Invited Talk)

Author Maximilien Gadouleau

PDF
Thumbnail PDF

File

OASIcs.AUTOMATA.2021.1.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Maximilien Gadouleau
  • Durham University, UK

Cite As Get BibTex

Maximilien Gadouleau. Dynamical Properties of Disjunctive Boolean Networks (Invited Talk). In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/OASIcs.AUTOMATA.2021.1

Abstract

A Boolean network is a mapping f :{0,1}ⁿ → {0,1}ⁿ, which can be used to model networks of n interacting entities, each having a local Boolean state that evolves over time according to a deterministic function of the current configuration of states. In this paper, we are interested in disjunctive networks, where each local function is simply the disjunction of a set of variables. As such, this network is somewhat homogeneous, though the number of variables may vary from entity to entity, thus yielding a generalised cellular automaton. The aim of this paper is to review some of the main results, derive some additional fundamental results, and highlight some open problems on the dynamics of disjunctive networks. We first review the different defining characteristics of disjunctive networks and several ways of representing them using graphs, Boolean matrices, or binary relations. We then focus on three dynamical properties of disjunctive networks: their image points, their periodic points, and their fixed points. For each class of points, we review how they can be characterised and study how many they could be. The paper finishes with different avenues for future work on the dynamics of disjunctive networks and how to generalise them.

Subject Classification

ACM Subject Classification
  • Applied computing → Biological networks
  • Hardware → Quantum dots and cellular automata
Keywords
  • Boolean networks
  • disjunction
  • conjunction
  • fixed points
  • rank

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. J.A. Aledo, S. Martínez, F.L. Pelayo, and Jose C. Valverde. Parallel discrete dynamical systems on maxterm and minterm boolean functions. Mathematical and Computer Modelling, 55:666-671, 2012. Google Scholar
  2. J. Aracena, J. Demongeot, and Eric Goles. Fixed points and maximal independent sets in AND-OR networks. Discrete Applied Mathematics, 138:277-288, 2004. Google Scholar
  3. J. Aracena, A. Richard, and L. Salinas. Maximum number of fixed points in and-or-not networks. Journal of Computer and System Sciences, 80(7):1175-1190, 2014. URL: https://doi.org/10.1016/j.jcss.2014.04.025.
  4. Julio Aracena. Maximum number of fixed points in regulatory Boolean networks. Bulletin of mathematical biology, 70:1398-1409, 2008. Google Scholar
  5. Julio Aracena, Jacques Demongeot, and Eric Goles. On limit cycles of monotone functions with symmetric connection graph. Theoretical Computer Science, 322:237-244, 2004. Google Scholar
  6. Julio Aracena, Jacques Demongeot, and Eric Goles. Positive and negative circuits in discrete neural networks. IEEE Transactions on Neural Networks, 15(1):77-83, January 2004. Google Scholar
  7. Julio Aracena, Adrien Richard, and Lilian Salinas. Number of fixed points and disjoint cycles in monotone boolean networks. SIAM journal on Discrete mathematics, 31(3):1702-1725, 2017. Google Scholar
  8. Jorgen Bang-Jensen and Gregory Gutin. Digraphs: Theory, Algorithms and Applications. Springer, 2009. Google Scholar
  9. Endre Boros. Boolean functions, chapter Horn functions, pages 269-321. Cambridge University Press, 2011. Google Scholar
  10. Kim Ki-Hang Butler. The number of idempotents in (0,1)-matrix semigroups. Linear Algebra and its Applications, 5:233-246, 1972. Google Scholar
  11. Peter J. Cameron. Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, Cambridge, UK, 1994. Google Scholar
  12. O. Colón-Reyes, R. Laubenbacher, and B. Pareigis. Boolean monomial dynamical systems. Annals of Combinatorics, 8(4):425-439, 2005. Google Scholar
  13. Omar Colón-Reyes, Abdul Salam Jarrah, Reinhard Laubenbacher, and Bernd Sturmfels. Monomial dynamical systems over finite fields. Complex Systems, 16:333-342, 2006. Google Scholar
  14. Maximilien Gadouleau. On the rank and periodic rank of finite dynamical systems. Electronic Journal of Combinatorics, 25(3):1-16, 2018. Google Scholar
  15. Maximilien Gadouleau. On the influence of the interaction graph on a finite dynamical system. Natural Computing, 19:15–28, 2020. Google Scholar
  16. Maximilien Gadouleau and Adrien Richard. Simple dynamics on graphs. Theoretical Computer Science, 628:62-77, 2016. Google Scholar
  17. Maximilien Gadouleau, Adrien Richard, and Søren Riis. Fixed points of boolean networks, guessing graphs, and coding theory. SIAM Journal on Discrete Mathematics, 29(4):2312-2335, 2015. Google Scholar
  18. E. Goles and M. Noual. Disjunctive networks and update schedules. Advances in Applied Mathematics, 48(5):646-662, 2012. Google Scholar
  19. E. Goles and J. Olivos. Comportement périodique des fonctions à seuil binaires et applications. Discrete Applied Mathematics, 3:93-105, 1981. Google Scholar
  20. Eric Goles. Dynamics of positive automata networks. Theoretical Computer Science, 41:19-32, 1985. Google Scholar
  21. Eric Goles and Gonzalo Hernández. Dynamical behavior of Kauffman networks with AND-OR gates. Journal of Biological Systems, 8(2):151-175, 2000. Google Scholar
  22. Eric Goles and M. Tchuente. Iterative behaviour of generalized majority functions. Mathematical Social Sciences, 4:197-204, 1983. Google Scholar
  23. Siegfried Gottwald. A Treatise on Many-Valued Logics. Research Studies Press Ltd., Baldock, Hertfordshire, England, 2001. Google Scholar
  24. Karl-Peter Hadeler and Johannes Müller. Cellular Automata: Analysis and Applications. Springer, Cham, Switzerland, 2017. Google Scholar
  25. Lisa Hellerstein. Boolean functions, chapter Characterizations of special classes by functional equations, pages 487-506. Cambridge University Press, 2011. Google Scholar
  26. John M. Howie. Fundamentals of Semigroup Theory. Oxford Science Publications, 1995. Google Scholar
  27. Andrew Ilachinski. Cellular Automata: A Discrete Universe. World Scientific, Singapore, 2001. Google Scholar
  28. A. Salam Jarrah, R. Laubenbacher, and A. Veliz-Cuba. The dynamics of conjunctive and disjunctive boolean network models. Bulletin of Mathematical Biology, 72:1425-1447, 2010. Google Scholar
  29. S. Kauffman, C. Peterson, B. Samuelsson, and C. Troein. Genetic networks with canalyzing boolean rules are always stable. Proceedings of the National Academy of Sciences of the United States of America, 101:17102-17107, 2004. Google Scholar
  30. Ki Hang Kim. Boolean Matrix Theory and Applications. Marcel Dekker, Inc., New York, 1982. Google Scholar
  31. Loïc Paulevé and Adrien Richard. Static analysis of boolean networks based on interaction graphs: A survey. Electronic Notes in Theoretical Computer Science, 284:93-104, 2012. Google Scholar
  32. Reinhard Pöschel and Ivo Rosenberg. Boolean models and methods in mathematics, computer science, and engineering, chapter Compositions and clones of Boolean functions, pages 3-38. Cambridge University Press, 2010. Google Scholar
  33. Søren Riis. Utilising public information in network coding. In General Theory of Information Transfer and Combinatorics, volume 4123/2006 of Lecture Notes in Computer Science, pages 866-897. Springer, 2006. Google Scholar
  34. F. Robert. Iterations sur des ensembles finis et automates cellulaires contractants. Linear Algebra and its Applications, 29:393-412, 1980. Google Scholar
  35. David Rosenblatt. On the graphs of finite idempotent boolean relation matrices. Journal of Research of the National Bureau of Standards-B. Mathematics and Mathematical Physics, 67B(4):259-256, October-December 1963. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact