Abstract
Reaction systems are a recent formal model inspired by the chemical reactions that happen inside cells and possess many different dynamical behaviours. In this work we continue a recent investigation of the complexity of detecting some interesting dynamical behaviours in reaction system. We prove that detecting global behaviours such as the presence of global attractors is PSPACE - complete. Deciding the presence of cycles in the dynamics and many other related problems are also PSPACE - complete. Deciding bijectivity is, on the other hand, a coNP - complete problem.
This work has been supported by the French National Research Agency project EMC (ANR-09-BLAN-0164) and by Fondo d’Ateneo (FA) 2013 of Università degli Studi di Milano-Bicocca: “Complessità computazionale in modelli di calcolo bioispirati: Sistemi a membrane e sistemi a reazioni”.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barrett, C.L., Hunt III, H.B., Marathe, M.V., Ravi, S., Rosenkrantz, D.J., Stearns, R.E.: Complexity of reachability problems for finite discrete dynamical systems. Int. J. Found. Comput. Sci. 72(8), 1317–1345 (2006)
Brijder, R., Ehrenfeucht, A., Rozenberg, G.: Reaction systems with duration. In: Kelemen, J., Kelemenová, A. (eds.) Pǎun Festschrif. LNCS, vol. 6610, pp. 191–202. Springer, Heidelberg (2011)
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(03), 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)
Formenti, E., Manzoni, L., Porreca, A.E.: Fixed points and attractors of reaction systems. In: Beckmann, A., Csuhaj-Varjú, E., Meer, K. (eds.) CiE 2014. LNCS, vol. 8493, pp. 194–203. Springer, Heidelberg (2014)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979)
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)
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)
Salomaa, A.: Functions and sequences generated by reaction systems. Theoretical Computer Science 466, 87–96 (2012)
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)
Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks. Natural Computing 7, 615–633 (2008)
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). Cycles and Global Attractors of Reaction Systems. In: Jürgensen, H., Karhumäki, J., Okhotin, A. (eds) Descriptional Complexity of Formal Systems. DCFS 2014. Lecture Notes in Computer Science, vol 8614. Springer, Cham. https://doi.org/10.1007/978-3-319-09704-6_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-09704-6_11
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09703-9
Online ISBN: 978-3-319-09704-6
eBook Packages: Computer ScienceComputer Science (R0)