<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume8 Issue4" %>
Boolean Monomial Dynamical Systems
Omar Colón-Reyes1, Reinhard Laubenbacher1, and Bodo Pareigis2
1Virginia Bioinformatics Institute, Virginia Tech, Blacksburg, VA 24061-0477, USA
ocolonre@calvin.math.vt.edu, reinhard@vbi.vt.edu
2Mathematisches Institut der Universität München, 80333 München, Germany
Annals of Combinatorics 8 (4) p.425-439 December, 2004
AMS Subject Classification: 37F20, 37B15, 05C20, 11T06, 68R05, 68U20
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.
Keywords: polynomial dynamical system, finite field, state space structure


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.