Complexity of model checking for reaction systems

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...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2016-04, Vol.623, p.103-113
Main Authors: Azimi, Sepinoud, Gratie, Cristian, Ivanov, Sergiu, Manzoni, Luca, Petre, Ion, Porreca, Antonio E.
Format: Article
Language:English
Subjects:
Biomodeling
Cells (biology)
Complexity
Complexity classes
Computer simulation
Conserved sets
Elementary flux
Fluxes
Formalism
Invariants
Mathematical models
Model checking
Periodicity
Reaction systems
Stationary process
Steady state
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2015.11.040