Composable computation in discrete chemical reaction networks
Composable computation in discrete chemical reaction networks
复制标题
离散化学反应网络中的可组合计算
DOI：
10.1007/s00446-020-00378-z
复制
发表时间：
2020
影响因子：
1.3
通讯作者：
Doty, David
中科院分区：
文献类型：
--
作者：
Severson, Eric E.;Haley, David;Doty, David
我们研究了稳定计算的离散化学反应网络（CRN）的可组合性（即，错误概率为0）整数值函数Nd：Nd→ N。我们考虑输出不经意的CRN，其中输出物种从来不是任何反应的反应物（输入）。输出不经意CRN类是基本的，出现在早期的CRN计算的研究，因为它正是CRN类，可以组成简单的重命名的上游CRN的输出，以匹配下游CRN的输入。我们的主要定理精确地刻画了函数f稳定可计算的输出不经意CRN与初始领导人。关键的必要条件是，对于足够大的输入，f是有限个非减quilt-affine函数的最小值。(An仿射函数是具有恒定偏移的线性函数;面组仿射函数是具有周期性偏移的线性函数）。
We study the composability of discrete chemical reaction networks (CRNs) that stably compute (i.e., with probability 0 of error) integer-valued functions ƒ:Nd→ N. We consider output-oblivious CRNs in which the output species is never a reactant (input) to any reaction. The class of output-oblivious CRNs is fundamental, appearing in earlier studies of CRN computation, because it is precisely the class of CRNs that can be composed by simply renaming the output of the upstream CRN to match the input of the downstream CRN.Our main theorem precisely characterizes the functions f stably computable by output-oblivious CRNs with an initial leader. The key necessary condition is that for sufficiently large inputs, f is the minimum of a finite number of nondecreasing quilt-affine functions. (An affine function is linear with a constant offset; a quilt-affine function is linear with a periodic offset).
登录
查看更多内容
DOI：
--
发表时间：
2012
期刊：
MOS-SIAM Series on Optimization
影响因子：
--
作者：
J. D. Loera;R. Hemmecke;M. Köppe
通讯作者：
M. Köppe
影响因子：
1.3
作者：
Angluin, Dana;Aspnes, James;Eisenstat, David
通讯作者：
Eisenstat, David
群体协议中的快速空间最优领导者选举
DOI：
10.1137/1.9781611975031.169
发表时间：
2017
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
L. Gąsieniec;Grzegorz Stachowiak
通讯作者：
Grzegorz Stachowiak
Petri 网和交换半群的指数空间完备问题（初步报告）
DOI：
--
发表时间：
1976
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
E. Cardoza;R. Lipton;A. Meyer
通讯作者：
A. Meyer
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
Dan Alistarh;J. Aspnes;David Eisenstat;Rati Gelashvili;Ronald L. Rivest
通讯作者：
Ronald L. Rivest