• 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. TUCS Technical Reports 1122, TUCS, 2014.

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.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tAzGrIvMaPePo14a,
  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.},
  number = {1122},
  series = {TUCS Technical Reports},
  publisher = {TUCS},
  year = {2014},
}

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

Edit publication