• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Complexity of Model Checking for Reaction Systems

Sepinoud Azimi, Cristian Gratie, Sergiu Ivanov, Luca Manzoni, Ion Petre, Antonio E. Porreca, Complexity of Model Checking for Reaction Systems. Theoretical Computer Science 623, 103–113, 2016.

http://dx.doi.org/10.1016/j.tcs.2015.11.040

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.

BibTeX entry:

@ARTICLE{jAzGrIvMaPePo16a,
  title = {Complexity of Model Checking for Reaction Systems},
  author = {Azimi, Sepinoud and Gratie, Cristian and Ivanov, Sergiu and Manzoni, Luca and Petre, Ion and Porreca, Antonio E.},
  journal = {Theoretical Computer Science},
  volume = {623},
  publisher = {Elsevier B.V.},
  pages = {103–113},
  year = {2016},
  keywords = {Reaction systems, Model checking, Biomodeling, Conserved sets, Invariants, Steady state, Stationary process, Elementary flux, Periodicity, Complexity classes},
  ISSN = {0304-3975},
}

Belongs to TUCS Research Unit(s): Computational Biomodeling Laboratory (Combio Lab)

Publication Forum rating of this publication: level 2

Edit publication