Complexity of model checking for reaction systems

A1 Journal article (refereed)


Internal Authors/Editors


Publication Details

List of Authors: Sepinoud Azimi, Cristian Gratie, Sergiu Ivanov, Luca Manzoni, Ion Petre , Antonio E. Porreca
Publisher: Elsevier
Publication year: 2016
Journal: Theoretical Computer Science
Volume number: 623
Start page: 103
End page: 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.

Last updated on 2019-16-10 at 02:38