Output-Oblivious Stochastic Chemical Reaction Networks
Output-Oblivious Stochastic Chemical Reaction Networks
复制标题
忽略输出的随机化学反应网络
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
H. Hashemi
中科院分区：
文献类型：
--
作者：
Ben Chugg;A. Condon;H. Hashemi
我们对函数$f:\mathbb{N}^2 \右列\mathbb{N}$进行了分类，这些函数可由输出无关随机化学反应网络（CRNs）稳定计算，即输出种永远不是反应物的反应系统。虽然已知crn可以精确地稳定计算半线性函数，但这种crn有时依赖于最初产生过多的输出物种，然后消耗多余的物种以达到正确的稳定状态。这些CRN可能很难集成到更大的系统中：如果CRN $\mathcal{C}$的输出成为下游CRN $\mathcal{C}'$的输入，那么$\mathcal{C}'$可能会在$\mathcal{C}$稳定之前无意中消耗太多的输出。另一方面，如果$\mathcal{C}$是输出无关的，那么$\mathcal{C}'$可能会在$\mathcal{C}$的输出可用时立即使用它。在这项工作中，我们证明了一个半线性函数$f:\mathbb{N}^2 \rightarrow \mathbb{N}$是稳定可计算的，当且仅当它既是递增的，又是网格仿射的（直观地说，它的域是同余类），或者是一个有限的裂缝函数集合的最小值（直观地说，函数的行为类似于最小函数）。
We classify the functions $f:\mathbb{N}^2 \rightarrow \mathbb{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 $\mathcal{C}$ becomes the input to a downstream CRN $\mathcal{C}'$, then $\mathcal{C}'$ could inadvertently consume too many outputs before $\mathcal{C}$ stabilizes. If, on the other hand, $\mathcal{C}$ is output-oblivious then $\mathcal{C}'$ may consume $\mathcal{C}$'s output as soon as it is available. In this work we prove that a semilinear function $f:\mathbb{N}^2 \rightarrow \mathbb{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).