Boolean Monomial Dynamical Systems

Omar Colón-Reyes^{1}, Reinhard Laubenbacher^{1}, and Bodo Pareigis^{2}

ocolonre@calvin.math.vt.edu, reinhard@vbi.vt.edu

pareigis@lmu.de

Annals of Combinatorics 8 (4) p.425-439 December, 2004

Abstract:

An important problem in the theory of finite dynamical systems is to link the structure
of a system with its dynamics. This paper contains such a link for a family of nonlinear systems
over the field with two elements. For systems that can be described by monomials (including
Boolean AND systems), one can obtain information about the limit cycle structure from the
structure of the monomials. In particular, the paper contains a sufficient condition for a monomial
system to have only fixed points as limit cycles. This condition depends on the cycle structure of
the dependency graph of the system and can be verified in polynomial time.

References:

1. R. Albert and H.G. Othmer, The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in Drosophila melanogaster, J. Theoret. Biol. 223 (2003) 1--18.

2. C.L. Barrett and C.M. Reidys, Elements of a theory of simulation, I: sequential CA over random graphs, Appl. Math. Comput. 98 (1999) 241--259.

3. C.L. Barrett, H.S. Mortveit, and C.M. Reidys, Elements of a theory of computer simulation II: sequential dynamical systems, Appl. Math. Comput. 107 (2-3) (1999) 121--36.

4. C.L. Barrett, H.S. Mortveit, and C.M. Reidys, Elements of a theory of computer simulation III: equivalence of SDS, Appl. Math. Comput. 122 (2001) 325--340.

5. F. Celada and P.E. Seiden, A computer model of cellular interactions in the immune system, Immunol. Today 13 (1992) 56--62.

6. P. Cull, Linear analysis of switching nets, Kybernetika 8 (1971) 31--39.

7. B. Elspas, The theory of autonomous linear sequential networks, IRE Transactions on Circuit Theory CT-6 (1959) 45--60.

8. R. Germundsson, J. Gunnarsson, and J. Plantin, Symbolic algebraic discrete systems-- applied to the JAS39 fighter aircraft, technical report, Linköping University, Linköping, Sweden, December, 1994.

9. R.A. Hernández Toledo, Linear Finite Dynamical Systems, preprint, 2003.

10. S.A. Kauffman, Metabolic stability and epigenesis in randomly constructed genetic nets, J. Theoret. Biol. 22 (1969) 437--467.

11. A. Khrennikov and M. Nilsson, On the number of cycles of *p*-adic dynamical systems, J.
Number Theory 90 (2001) 255--264.

12. R. Laubenbacher, A computer algebra approach to biological systems, Proc. Intl. Symp. Symbolic and Alg. Comp., Philadelphia, Assoc. Comp. Mach., 2003.

13. R. Laubenbacher and B. Pareigis, Equivalence relations on finite dynamical systems, Adv. Appl. Math. 26 (2001) 237--251.

14. R. Laubenbacher and B. Pareigis, Decomposition and simulation of sequential dynamical systems, Adv. Appl. Math. 30 (2003) 655--678.

15. R. Laubenbacher and B. Stigler, A computational algebra approach to the reverseengineering of gene regulatory networks, J. Theoret. Biol. 229 (2004) 523--537.

16. R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia of Math and its Appl, 20, Cambridge University Press, London, 1997.

17. H. Marchand and M. LeBorgne, On the optimal control of polynomial dynamical systems
over *Z*/*p*, Fourth workshop on Discrete Event Systems, Cagliari, Italy, IEEE, 1998.

18. H. Marchand and M. LeBorgne, Partial order discrete event systems modeled as polynomial dynamical systems, IEEE Intl. Conf. on Control Applications, Trieste, Italy, 1998.

19. D.K. Milligan and M.J.D. Wilson, The behaviour of affine sequential Boolean networks, Connection Science 5 (1993) 153--167.

20. S. Wolfram, Cellular Automata and Complexity, Westview Press, 1994.