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.
Cycles and global attractors of reaction systems / Formenti, Enrico; Manzoni, Luca; Porreca Antonio, E.. - STAMPA. - 8614:(2014), pp. 114-125. ( 16th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2014 Turku, fin 2014) [10.1007/978-3-319-09704-6_11].
Cycles and global attractors of reaction systems
Manzoni Luca;
2014-01-01
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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
