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. (2016). Complexity of model checking for reaction systems. THEORETICAL COMPUTER SCIENCE, 623, 103-113 [10.1016/j.tcs.2015.11.040].

Complexity of model checking for reaction systems

MANZONI, LUCA;PORRECA, ANTONIO ENRICO
Ultimo
2016

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.
Articolo in rivista - Articolo scientifico
Biomodeling; Complexity classes; Conserved sets; Elementary flux; Invariants; Model checking; Periodicity; Reaction systems; Stationary process; Steady state;
Biomodeling; Complexity classes; Conserved sets; Elementary flux; Invariants; Model checking; Periodicity; Reaction systems; Stationary process; Steady state
English
103
113
11
Azimi, S., Gratie, C., Ivanov, S., Manzoni, L., Petre, I., Porreca, A. (2016). Complexity of model checking for reaction systems. THEORETICAL COMPUTER SCIENCE, 623, 103-113 [10.1016/j.tcs.2015.11.040].
Azimi, S; Gratie, C; Ivanov, S; Manzoni, L; Petre, I; Porreca, A
File in questo prodotto:
File Dimensione Formato  
Paper.pdf

accesso aperto

Descrizione: Preprint
Dimensione 397.09 kB
Formato Adobe PDF
397.09 kB Adobe PDF Visualizza/Apri

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/134883
Citazioni
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 18
Social impact