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.
Formenti, E., Manzoni, L., Porreca, A. (2014). Cycles and global attractors of reaction systems. In Descriptional Complexity of Formal Systems, 16th International Workshop, DCFS 2014 (pp.114-125). Springer [10.1007/978-3-319-09704-6_11].
Cycles and global attractors of reaction systems
MANZONI, LUCA;PORRECA, ANTONIO ENRICO
2014
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.
| File | Dimensione | Formato | |
|---|---|---|---|
|
Paper.pdf
Solo gestori archivio
Dimensione
302.87 kB
Formato
Adobe PDF
|
302.87 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
