Leaderless deterministic chemical reaction networks
Leaderless deterministic chemical reaction networks
复制标题
无领导的确定性化学反应网络
DOI：
10.1007/s11047-014-9435-8
复制
发表时间：
2013
影响因子：
2.1
通讯作者：
Monir Hajiaghayi
中科院分区：
文献类型：
--
作者：
David Doty;Monir Hajiaghayi
本文回答了Chen等人（DNA 2012：Proceedings of the 18 th International Conference on DNA Computing and Molecular Programming，Vol 7433 of Lecture Notes in Computer Science）的一个开放性问题。Springer，柏林，pp 25-42，2012），他证明了一个函数$$f：\mathbb {N}^k\rightarrow \mathbb {N}^l$$f：Nk→Nl是随机化学反应网络（CRN）确定性可计算的当且仅当$$f$$f的图是$\mathbb {N}^{k+l}$$Nk+l的半线性子集。该构造关键地使用了“领导者”：能够在初始配置中以恒定但非零的物种计数开始，而不是代表函数$$f$$f的输入的$$k$$k物种$$X_1，\ldots，X_k$X1，.，Xk。作者询问没有领导者的确定性CRN是否保持相同的权力。我们肯定地回答了这个问题，证明了每个半线性函数都可以由CRN确定地计算，CRN的初始配置只包含输入物种X1，Xk，X1，.，Xk，其他物种的计数为零，只要f（{\bf 0}）={\bf 0} f（0）=0。我们证明了这个CRN在预期时间内完成$$O（n）$$O（n），其中$$n$$n是输入分子的总数。这个时间界限比Chen et al.（2012）实现的$$O（\log ^5 n）$$O（log 5 n）慢，但比Chen et al.（2012）直接构造实现的$$O（n \log n）$$O（nlogn）快。
This paper answers an open question of Chen et al. (DNA 2012: proceedings of the 18th international meeting on DNA computing and molecular programming, vol 7433 of lecture notes in computer science. Springer, Berlin, pp 25–42, 2012), who showed that a function $$f:\mathbb {N}^k\rightarrow \mathbb {N}^l$$f:Nk→Nl is deterministically computable by a stochastic chemical reaction network (CRN) if and only if the graph of $$f$$f is a semilinear subset of $$\mathbb {N}^{k+l}$$Nk+l. That construction crucially used “leaders”: the ability to start in an initial configuration with constant but non-zero counts of species other than the $$k$$k species $$X_1,\ldots ,X_k$$X1,…,Xk representing the input to the function $$f$$f. The authors asked whether deterministic CRNs without a leader retain the same power. We answer this question affirmatively, showing that every semilinear function is deterministically computable by a CRN whose initial configuration contains only the input species $$X_1,\ldots ,X_k$$X1,…,Xk, and zero counts of every other species, so long as $$f({\bf 0})={\bf 0}$$f(0)=0. We show that this CRN completes in expected time $$O(n)$$O(n), where $$n$$n is the total number of input molecules. This time bound is slower than the $$O(\log ^5 n)$$O(log5n) achieved in Chen et al. (2012), but faster than the $$O(n \log n)$$O(nlogn) achieved by the direct construction of Chen et al. (2012).