Complexity of model checking for reaction systems

详细信息    查看全文

• 作者：Sepinoud Azimi^a ; ^{sazimi@abo.fi" class="auth_mail" title="E-mail the corresponding author} ; Cristian Gratie^a ; ^{cgratie@abo.fi" class="auth_mail" title="E-mail the corresponding author} ; Sergiu Ivanov^c ; ^{sergiu.ivanov@u-pec.fr" class="auth_mail" title="E-mail the corresponding author} ; Luca Manzoni^b ; ^{luca.manzoni@disco.unimib.it" class="auth_mail" title="E-mail the corresponding author} ; Ion Petre^a ; ^{ipetre@abo.fi" class="auth_mail" title="E-mail the corresponding author} ; Antonio E. Porreca^b ; ^{porreca@disco.unimib.it" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Reaction systems ; Model checking ; Biomodeling ; Conserved sets ; Invariants ; Steady state ; Stationary process ; Elementary flux ; Periodicity ; Complexity classes
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：11 April 2016
• 年：2016
• 卷：623
• 期：Complete
• 页码：103-113
• 全文大小：373 K

文摘

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$\mathsf{P}$ to NP$\mathsf{NP}$- and coNP$\mathsf{coNP}$-complete to PSPACE$\mathsf{PSPACE}$-complete.