Azimi, S., Gratie, C., Ivanov, S., Manzoni, L., Petre, I., & Porreca, A. E. (2016). Complexity of model checking for reaction systems. Theoretical Computer Science, 623, 103-113.
Abstract
Reaction systems are a new mathematical formalism inspired by the living cell and driven by only two basic mechanisms: facilitation and inhibition. As a modeling framework, they differ from the traditional approaches based on ODEs and CTMCs in two fundamental aspects: their qualitative character and the non-permanency of resources. In this article we introduce to reaction systems several notions of central interest in biomodeling: mass conservation, invariants, steady states, stationary processes, elementary fluxes, and periodicity. We prove that the decision problems related to these properties span a number of complexity classes from P to NP- and coNP-complete to PSPACE-complete.
@article{azimi2016complexity,
title={Complexity of model checking for reaction systems},
author={Azimi, Sepinoud and Gratie, Cristian and Ivanov, Sergiu and Manzoni, Luca and Petre, Ion and Porreca, Antonio E},
journal={Theoretical Computer Science},
volume={623},
pages={103--113},
year={2016},
publisher={Elsevier}
}
Azimi, S., Gratie, C., Ivanov, S., Manzoni, L., Petre, I., & Porreca, A. E. (2016). Complexity of model checking for reaction systems. Theoretical Computer Science, 623, 103-113.
Abstract Reaction systems are a new mathematical formalism inspired by the living cell and driven by only two basic mechanisms: facilitation and inhibition. As a modeling framework, they differ from the traditional approaches based on ODEs and CTMCs in two fundamental aspects: their qualitative character and the non-permanency of resources. In this article we introduce to reaction systems several notions of central interest in biomodeling: mass conservation, invariants, steady states, stationary processes, elementary fluxes, and periodicity. We prove that the decision problems related to these properties span a number of complexity classes from P to NP- and coNP-complete to PSPACE-complete.
Link to the online copy
Bibtex file
@article{azimi2016complexity, title={Complexity of model checking for reaction systems}, author={Azimi, Sepinoud and Gratie, Cristian and Ivanov, Sergiu and Manzoni, Luca and Petre, Ion and Porreca, Antonio E}, journal={Theoretical Computer Science}, volume={623}, pages={103--113}, year={2016}, publisher={Elsevier} }