Abstract
We investigate the computational complexity of deciding the occurrence of many different dynamical behaviours in reaction systems, with an emphasis on biologically relevant problems (i.e., existence of fixed points and fixed point attractors). We show that the decision problems of recognising these dynamical behaviours span a number of complexity classes ranging from FO-uniform AC 0 to \({\Pi_2^{\rm P}}\)-completeness with several intermediate problems being either NP or coNP-complete.
This work has been partially supported by the French National Research Agency project EMC (ANR-09-BLAN-0164).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bornholdt, S.: Boolean network models of cellular regulation: prospects and limitations. J. R. Soc. Interface 5, S84–S94 (2008)
Corolli, L., Maj, C., Marini, F., Besozzi, D., Mauri, G.: An excursion in reaction systems: From computer science to biology. Theor. Comp. Sci. 454, 95–108 (2012)
Ehrenfeucht, A., Main, M., Rozenberg, G.: Combinatorics of life and death for reaction systems. Int. J. Found. Comput. Sci. 21(3), 345–356 (2010)
Ehrenfeucht, A., Main, M., Rozenberg, G.: Functions defined by reaction systems. Int. J. Found. Comput. Sci. 22(1), 167–168 (2011)
Ehrenfeucht, A., Rozenberg, G.: Reaction systems. Fundam. Inform. 75, 263–280 (2007)
Immerman, N.: Descriptive Complexity. Graduate Texts in Computer Science. Springer (1999)
Kauffman, S.A.: Metabolic stability and epigenesis in randomly constructed genetic nets. J. Theor. Biol. 22(3), 437–467 (1969)
Kauffman, S.A.: The ensemble approach to understand genetic regulatory networks. Physica A: Statistical Mechanics and its Applications 340(4), 733–740 (2004)
Kitano, H.: Biological robustness. Nature Reviews Genetics 5, 826–837 (2004)
Papadimitriou, C.H.: Computational Complexity. Addison-Wesley (1993)
Păun, G.: Computing with membranes. Journal of Computer and System Sciences 61(1), 108–143 (2000)
Păun, Gh., Pérez-Jiménez, M.J., Rozenberg, G.: Bridging membrane and reaction systems – Further results and research topics. Fundam. Inform. 127, 99–114 (2013)
Salomaa, A.: Functional constructions between reaction systems and propositional logic. Int. J. Found. Comput. Sci. 24(1), 147–159 (2013)
Salomaa, A.: Minimal and almost minimal reaction systems. Natural Computing 12(3), 369–376 (2013)
Shmulevich, I., Dougherty, E.R.: Probabilistic boolean networks: the modeling and control of gene regulatory networks. SIAM (2010)
Shmulevich, I., Dougherty, E.R., Zhang, W.: From Boolean to probabilistic Boolean networks as models of genetic regulatory networks. Proceedings of the IEEE 90(11), 1778–1792 (2002)
Stockmeyer, L.J.: The polynomial-time hierarchy. Theor. Comp. Sci. 3(1), 1–22 (1976)
Thachuk, C., Condon, A.: Space and energy efficient computation with DNA strand displacement systems. In: Stefanovic, D., Turberfield, A. (eds.) DNA 2012. LNCS, vol. 7433, pp. 135–149. Springer, Heidelberg (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Formenti, E., Manzoni, L., Porreca, A.E. (2014). Fixed Points and Attractors of Reaction Systems. In: Beckmann, A., Csuhaj-Varjú, E., Meer, K. (eds) Language, Life, Limits. CiE 2014. Lecture Notes in Computer Science, vol 8493. Springer, Cham. https://doi.org/10.1007/978-3-319-08019-2_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-08019-2_20
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08018-5
Online ISBN: 978-3-319-08019-2
eBook Packages: Computer ScienceComputer Science (R0)