Chitkara University Publications

Monomial Dynamical Systems in # P-complete

Abstract:

In this paper, we study boolean monomial dynamical systems. Colón-Reyes, Jarrah, Laubenbacher, and Sturmfels(2006) studied fixed point structure of boolean monomial dynamical systems of f by associating the dynamical systems of f with its dependency graph χf and Jarrah, Laubenbacher, and Veliz-Cuba(2010) extended it and presented lower and upper bound for the number of cycles of a given length for general boolean monomial dynamics. But, it is even difficult to determine the exact number of fixed points of boolean monomial dynamics. We show that the problem of counting fixed points of a boolean monomial dynamical systems is #P-complete, for which no efficient algorithm is known. This is proved by a 1-1 correspondence between fixed points of f sand antichains of the poset of strongly connected components of χf..

Author(s):

  • Jang-Woo Park, School of Arts & Sciences, University of Houston – Victoria, Victoria, TX 77901, USA
  • Shuhong Gao, Department of Mathematical Sciences, Clemson University, Clemson, SC 29634-0975, USA

DOI: 

Keywords: 

preperiodic, monomial dynamics, directed path

References:

Barta, A. and Morton, P., 1994. Algebraic dynamics of polynomial maps on the algebraic closure of a finite field,I. Rocky Mountain Journal of Mathematics, 24(2), pp.453-481. http://dx.doi.org/10.1216/rmjm/1181072411

Barta, A. and Morton, P., 1994.Algebraic dynamics of polynomial maps on the algebraic closure of a finite field,II. Rocky Mountain Journal of Mathematics, 24(3), pp.905-932. http://dx.doi.org/10.1216/rmjm/1181072380

Colón-Reyes, O., Jarrah, A.S., Laubenbacher, R., and Sturmfels, B., 2006.Monomial dynamical systems over finite fields. Journal of Complex Systems, 16(4), pp.333-342.

Devaney, R.L., 2003.An Introduction to Chaotic Dynamical System. 2nd ed. Westview Press.

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

Gilbert, C.L., Kolesar, J.D., Reiter, C.A., and Stroey, J.D., 2001. Function digraphs of quadratic maps modulo p. The Fibonacci Quarterly, 39, pp.32-49.

Hernandez-Toledo, R.A., 2005. Linear finite dynamical systems. Communications in Algebra, 33(9), pp.2977-2989. http://dx.doi.org/10.1081/AGB-200066211

Jarrah, A.S., Laubenbacher, R., and Vera-Licona. P., 2006.An efficient algorithm for finding the phase space structure of linear finite dynamical systems. preprint.

Jarrah, A.S., Laubenbacher, R., and Veliz-Cuba,A., 2010. The dynamics of conjunctive and disjunctive boolean networks. Bulletin of Mathematical Biology, 72(6), pp.1425-1447. http://dx.doi.org/10.1007/s11538-010-9501-z

Just, W.,2006. The steady state system problem is NP-hard even for monotone quadratic Boolean dynamical systems.preprints available at http://www.ohio.edu/people/just/PAPERS/monNPh14.

Knuth, D.E. and Rusky, F., 2003. Efficient Coroutine Generation of Constrained Gray Sequences. Lecture Notes in Computer Science, 2635, pp.183-208. http://dx.doi.org/10.1007/978-3-540-39993-3_11

Park, J.W., 2003. Algebraic properties of the digraph generated by the iteration of quadratic mapping xx2 −2(mod p). manuscript.

Provan, J.S. and Ball, M.O., 1983. Complexity of Counting Cuts, Siam Journal of Computing 12 pp.777-788. http://dx.doi.org/10.1137/0212053

Robinson, C., 1998.Dynamical Systems – Stability, Symbolic Dynamics, and Chaos. CRC.

Rogers, T.D., 1996, The graph of the square mapping on the prime fields,Discrete Mathematics, 148, pp.317-324. http://dx.doi.org/10.1016/0012-365X(94)00250-M

Vasiga, T. and Shallit, J., 2004, On the iteration of certain quadratic maps over GF(p), Discrete Mathematics, 277, pp.219-240. http://dx.doi.org/10.1016/S0012-365X(03)00158-4

Xua, G.and Zoub, Y.M., 2009, Linear dynamical systems over finite rings.Journal of Algebra, 321(8), pp.2149-2155. http://dx.doi.org/10.1016/j.jalgebra.2008.09.029

Valiant, L.G., 1979, The Complexity of Computing the Permanent.Theoretical Computer Science, 8, pp.189-201 http://dx.doi.org/10.1016/0304-3975(79)90044-6

Zieve, M.E., 1996.Cycles of polynomial mappings. Ph.D. thesis, University of California at Berkeley.

 

 

0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
CHITKARA UNIVERSITY ADMINISTRATIVE OFFICE SARASWATI KENDRA, PO Box No. 70 SCO – 160-161,Sector – 9C, Chandigarh – 160009, India. +91-172-2741000, +91-172-4691800 chitkarauniversitypublications@chitkara.edu.in

    0
    Would love your thoughts, please comment.x
    ()
    x