Formenti, E., Manzoni, L., & Porreca, A. E. (2014, August). Cycles and global attractors of reaction systems. In International Workshop on Descriptional Complexity of Formal Systems (pp. 114-125). Springer, Cham.
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.
Bibtex file
@inproceedings{formenti2014cycles,
title={Cycles and global attractors of reaction systems},
author={Formenti, Enrico and Manzoni, Luca and Porreca, Antonio E},
booktitle={International Workshop on Descriptional Complexity of Formal Systems},
pages={114--125},
year={2014},
organization={Springer}
}
Formenti, E., Manzoni, L., & Porreca, A. E. (2014, August). Cycles and global attractors of reaction systems. In International Workshop on Descriptional Complexity of Formal Systems (pp. 114-125). Springer, Cham.
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.
Link to the online copy
Bibtex file @inproceedings{formenti2014cycles, title={Cycles and global attractors of reaction systems}, author={Formenti, Enrico and Manzoni, Luca and Porreca, Antonio E}, booktitle={International Workshop on Descriptional Complexity of Formal Systems}, pages={114--125}, year={2014}, organization={Springer} }