Complexity of Model Checking for Reaction Systems

Sepinoud Azimi Rashti, Cristian Gratie, Sergiu Ivanov, Luca Manzoni, Ion Petre, Antonio E. Porreca

    Tutkimustuotos: Kirja/lehti/raporttiTutkimusraporttiAmmatillinen

    Abstrakti

    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.
    AlkuperäiskieliEi tiedossa
    KustantajaTurku Centre for Computer Science (TUCS)
    ISBN (painettu)978-952-12-3122-3
    TilaJulkaistu - 2014
    OKM-julkaisutyyppiD4 Julkaistut kehitykset tai tutkimusraportit tai tutkimukset

    Keywords

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

    Viittausmuodot