Forward and backward bisimulations for chemical reaction networks

Luca Cardelli, Mirco Tribastone, Max Tschaikowski, Andrea Vandin

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

We present two quantitative behavioral equivalences over species of a chemical reaction network (CRN) with semantics based on ordinary differential equations. Forward CRN bisimulation identifies a partition where each equivalence class represents the exact sum of the concentrations of the species belonging to that class. Backward CRN bisimulation relates species that have identical solutions at all time points when starting from the same initial conditions. Both notions can be checked using only CRN syntactical information, i.e., by inspection of the set of reactions. We provide a unified algorithm that computes the coarsest refinement up to our bisimulations in polynomial time. Further, we give algorithms to compute quotient CRNs induced by a bisimulation. As an application, we find significant reductions in a number of models of biological processes from the literature. In two cases we allow the analysis of benchmark models which would be otherwise intractable due to their memory requirements.

Original languageEnglish
Title of host publication26th International Conference on Concurrency Theory, CONCUR 2015
Number of pages14
Volume42
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date1 Aug 2015
Pages226-239
ISBN (Electronic)9783939897910
DOIs
Publication statusPublished - 1 Aug 2015
Externally publishedYes
Event26th International Conference on Concurrency Theory, CONCUR 2015 - Madrid, Spain
Duration: 1 Sep 20154 Sep 2015

Conference

Conference26th International Conference on Concurrency Theory, CONCUR 2015
CountrySpain
CityMadrid
Period01/09/201504/09/2015

Keywords

  • Bisimulation
  • Chemical reaction networks
  • Ordinary differential equations
  • Partition refinement

Fingerprint Dive into the research topics of 'Forward and backward bisimulations for chemical reaction networks'. Together they form a unique fingerprint.

Cite this