Hashemi, Hooman ;
Chugg, Ben ;
Condon, Anne
Composable Computation in Leaderless, Discrete Chemical Reaction Networks
Abstract
We classify the functions f:ℕ^d → ℕ that are stably computable by leaderless, outputoblivious discrete (stochastic) Chemical Reaction Networks (CRNs). CRNs that compute such functions are systems of reactions over species that include d designated input species, whose initial counts represent an input x ∈ ℕ^d, and one output species whose eventual count represents f(x). Chen et al. showed that the class of functions computable by CRNs is precisely the semilinear functions. In outputoblivious CRNs, the output species is never a reactant. Outputoblivious CRNs are easily composable since a downstream CRN can consume the output of an upstream CRN without affecting its correctness. Severson et al. showed that outputoblivious CRNs compute exactly the subclass of semilinear functions that are eventually the minimum of quiltaffine functions, i.e., affine functions with different intercepts in each of finitely many congruence classes. They call such functions the outputoblivious functions. A leaderless CRN can compute only superadditive functions, and so a leaderless outputoblivious CRN can compute only superadditive, outputoblivious functions. In this work we show that a function f:ℕ^d → ℕ is stably computable by a leaderless, outputoblivious CRN if and only if it is superadditive and outputoblivious.
BibTeX  Entry
@InProceedings{hashemi_et_al:LIPIcs:2020:12956,
author = {Hooman Hashemi and Ben Chugg and Anne Condon},
title = {{Composable Computation in Leaderless, Discrete Chemical Reaction Networks}},
booktitle = {26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
pages = {3:13:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771634},
ISSN = {18688969},
year = {2020},
volume = {174},
editor = {Cody Geary and Matthew J. Patitz},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12956},
URN = {urn:nbn:de:0030drops129560},
doi = {10.4230/LIPIcs.DNA.2020.3},
annote = {Keywords: Chemical Reaction Networks, Stable Function Computation, OutputOblivious, OutputMonotonic}
}
04.09.2020
Keywords: 

Chemical Reaction Networks, Stable Function Computation, OutputOblivious, OutputMonotonic 
Seminar: 

26th International Conference on DNA Computing and Molecular Programming (DNA 26)

Issue date: 

2020 
Date of publication: 

04.09.2020 