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.OPODIS.2018.21
URN: urn:nbn:de:0030-drops-100815
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10081/
Go to the corresponding LIPIcs Volume Portal

Chugg, Ben ; Hashemi, Hooman ; Condon, Anne

Output-Oblivious Stochastic Chemical Reaction Networks

pdf-format:
LIPIcs-OPODIS-2018-21.pdf (0.6 MB)

Abstract

We classify the functions f:N^2 -> N which are stably computable by output-oblivious Stochastic Chemical Reaction Networks (CRNs), i.e., systems of reactions in which output species are never reactants. While it is known that precisely the semilinear functions are stably computable by CRNs, such CRNs sometimes rely on initially producing too many output species, and then consuming the excess in order to reach a correct stable state. These CRNs may be difficult to integrate into larger systems: if the output of a CRN C becomes the input to a downstream CRN C', then C' could inadvertently consume too many outputs before C stabilizes. If, on the other hand, C is output-oblivious then C' may consume C's output as soon as it is available. In this work we prove that a semilinear function f:N^2 -> N is stably computable by an output-oblivious CRN with a leader if and only if it is both increasing and either grid-affine (intuitively, its domains are congruence classes), or the minimum of a finite set of fissure functions (intuitively, functions behaving like the min function).

BibTeX - Entry

@InProceedings{chugg_et_al:LIPIcs:2018:10081,
  author =	{Ben Chugg and Hooman Hashemi and Anne Condon},
  title =	{{Output-Oblivious Stochastic Chemical Reaction Networks}},
  booktitle =	{22nd International Conference on Principles of Distributed  Systems (OPODIS 2018)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{125},
  editor =	{Jiannong Cao and Faith Ellen and Luis Rodrigues and Bernardo Ferreira},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10081},
  URN =		{urn:nbn:de:0030-drops-100815},
  doi =		{10.4230/LIPIcs.OPODIS.2018.21},
  annote =	{Keywords: Chemical Reaction Networks, Stable Function Computation, Output-Oblivious, Output-Monotonic}
}

Keywords: Chemical Reaction Networks, Stable Function Computation, Output-Oblivious, Output-Monotonic
Collection: 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)
Issue Date: 2018
Date of publication: 15.01.2019

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