文章基本信息

标题：Composable Computation in Leaderless, Discrete Chemical Reaction Networks
本地全文：下载
作者：Hooman Hashemi ; Ben Chugg ; Anne Condon 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：174
页码：3:1-3:18
DOI：10.4230/LIPIcs.DNA.2020.3
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We classify the functions f:â".^d â' â". that are stably computable by leaderless, output-oblivious 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 output-oblivious CRNs, the output species is never a reactant. Output-oblivious 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 output-oblivious CRNs compute exactly the subclass of semilinear functions that are eventually the minimum of quilt-affine functions, i.e., affine functions with different intercepts in each of finitely many congruence classes. They call such functions the output-oblivious functions. A leaderless CRN can compute only superadditive functions, and so a leaderless output-oblivious CRN can compute only superadditive, output-oblivious functions. In this work we show that a function f:â".^d â' â". is stably computable by a leaderless, output-oblivious CRN if and only if it is superadditive and output-oblivious.
关键词：Chemical Reaction Networks; Stable Function Computation; Output-Oblivious; Output-Monotonic