Complexity of model checking for reaction systems

Journal article (2016)

Authors

Sepinoud Azimi Åbo Akademi University
Cristian Gratie Åbo Akademi University
Sergiu Ivanov Université Paris-Est-Créteil
Luca Manzoni Università degli Studi di Milano Bicocca
Ion Petre Åbo Akademi University
Antonio E. Porreca Università degli Studi di Milano Bicocca
Affiliation
External organisation
Periodicity Model checking Biomodeling Complexity classes Conserved sets Elementary flux Invariants Reaction systems Stationary process Steady state
More Info
expand_more

Published Date

2016

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

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.