DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2015.226

Forward and Backward Bisimulations for Chemical Reaction Networks

Authors: Luca Cardelli, Mirco Tribastone, Max Tschaikowski, and Andrea Vandin

Published in: LIPIcs, Volume 42, 26th International Conference on Concurrency Theory (CONCUR 2015)

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.

Cite as

Luca Cardelli, Mirco Tribastone, Max Tschaikowski, and Andrea Vandin. Forward and Backward Bisimulations for Chemical Reaction Networks. In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 226-239, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{cardelli_et_al:LIPIcs.CONCUR.2015.226,
  author =	{Cardelli, Luca and Tribastone, Mirco and Tschaikowski, Max and Vandin, Andrea},
  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 =	{Aceto, Luca and de Frutos Escrig, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2015.226},
  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}
}

Search Results

Documents authored by Tribastone, Mirco

Forward and Backward Bisimulations for Chemical Reaction Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message