Complexity of Model Checking for Reaction Systems

D4 Publicerad utvecklings- eller forskningsrapport eller studie


Interna författare/redaktörer


Publikationens författare: Sepinoud Azimi, Cristian Gratie, Sergiu Ivanov, Luca Manzoni, Ion Petre, Antonio E. Porreca
Förläggare: Turku Centre for Computer Science (TUCS)
Publiceringsår: 2014
ISBN: 978-952-12-3122-3


Abstrakt

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.


Nyckelord

biomodeling, complexity classes, conserved set, elementary flux, invariants, model checking, periodicity, reaction system, stationary process, steady state

Senast uppdaterad 2019-10-12 vid 03:57