Complexity of Model Checking for Reaction Systems


Séminaire Modèles et Algorithmes Déterministes: CASYS

16/03/2017 - 09:30 Mr Sergiu Ivanov Salle 106 - Batiment IMAG

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