Monomial Dynamical Systems in # P-complete
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..
Barta, A. and Morton, P., 1994. Algebraic dynamics of polynomial maps on the algebraic closure of a ﬁnite ﬁeld,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 ﬁnite ﬁeld,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 ﬁnite ﬁelds. 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 ﬁnite 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 efﬁcient algorithm for ﬁnding the phase space structure of linear ﬁnite 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. Efﬁcient 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 ﬁelds,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 ﬁnite 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.
Copyright (c) 2012 Mathematical Journal of Interdisciplinary Sciences
This work is licensed under a Creative Commons Attribution 4.0 International License.
License and Copyright Policy
Chitkara University Publications for the journal (Math. J. Interdiscip. Sci.) protects author rights e.g., the results, analysis, methodology of Theoretical calculations or experiment. The copyright transfer form with open access policy under the creative common licenses of journal provides all rights specifically to the author (s); except to sell, distribution of the material in any form to any third party. Also, the authors are encouraged to submit the author’s copy of the accepted paper to an appropriate archive e.g. arxive.org and/or in their institution’s repositories, or on their personal website also.
Author(s) should mention reference of the Journal of Chitkara University Publications and DOI number of the publication carefully on the required page of the depository, in all above-mentioned cases. The copyright and license policy of Chitkara University Publications not only protect the author's rights but also protect the integrity and authenticity of the scientific records and takes very seriously about the plagiarism, fraud or ethics disputes.
Articles in Mathematical Journal of Interdisciplinary Sciences (Math. J. Interdiscip. Sci.) by Chitkara University Publications are Open Access articles that are published with licensed under a Creative Commons Attribution- CC-BY 4.0 International License. Based on a work at https://mjis.chitkara.edu.in. This license permits one to use, remix, tweak and reproduction in any medium, even commercially provided one give credit for the original creation.
View Legal Code of the above mentioned license, https://creativecommons.org/licenses/by/4.0/legalcode
View Licence Deed here https://creativecommons.org/licenses/by/4.0/
|Mathematical Journal of Interdisciplinary Sciences by Chitkara University Publications is licensed under a Creative Commons Attribution 4.0 International License. Based on a work at https://mjis.chitkara.edu.in|