License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2015.226
URN: urn:nbn:de:0030-drops-53684
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5368/
Go to the corresponding LIPIcs Volume Portal

Cardelli, Luca ; Tribastone, Mirco ; Tschaikowski, Max ; Vandin, Andrea

Forward and Backward Bisimulations for Chemical Reaction Networks

pdf-format:
8.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{cardelli_et_al:LIPIcs:2015:5368,
  author =	{Luca Cardelli and Mirco Tribastone and Max Tschaikowski and Andrea Vandin},
  title =	{{Forward and Backward Bisimulations for Chemical Reaction Networks}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{226--239},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Luca Aceto and David de Frutos Escrig},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5368},
  URN =		{urn:nbn:de:0030-drops-53684},
  doi =		{10.4230/LIPIcs.CONCUR.2015.226},
  annote =	{Keywords: Chemical reaction networks, ordinary differential equations, bisimulation, partition refinement}
}

Keywords: Chemical reaction networks, ordinary differential equations, bisimulation, partition refinement
Collection: 26th International Conference on Concurrency Theory (CONCUR 2015)
Issue Date: 2015
Date of publication: 26.08.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI