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.

Azimi, S., Gratie, C., Ivanov, S., Manzoni, L., Petre, I., & Porreca, A.E. (2014). Complexity of Model Checking for Reaction Systems [Rapporto tecnico].

Complexity of Model Checking for Reaction Systems

MANZONI, LUCA;PORRECA, ANTONIO ENRICO
2014

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.
Rapporto tecnico
Scientifica
Reaction systems; model checking; biomodeling; conserved sets; invariants; steady state; stationary process; elementary flux; periodicity; complexity classes
English
Azimi, S., Gratie, C., Ivanov, S., Manzoni, L., Petre, I., & Porreca, A.E. (2014). Complexity of Model Checking for Reaction Systems [Rapporto tecnico].
Azimi, S; Gratie, C; Ivanov, S; Manzoni, L; Petre, I; Porreca, A
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/107067
Citazioni
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
Social impact