Robustness of Expressivity in Chemical Reaction Networks
Robustness of Expressivity in Chemical Reaction Networks
复制标题
化学反应网络中表现力的鲁棒性
DOI：
10.1007/978-3-319-43994-5_4
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
D. Soloveichik
中科院分区：
文献类型：
--
作者：
R. Brijder;David Doty;D. Soloveichik
我们表明，一些自然的输出公约，在化学反应网络（CRN）的无错误计算导致一个共同的水平的计算表现力。我们的主要结果是，无错误CRN的标准定义具有与1）非对称和2）民主CRN等效的计算能力。前者只有“是”的投票者，如果有任何投票者在场，CRN的输出就是“是”，否则就是“否”。后者通过“赞成”和“反对”选民的多数票来定义产出。
这两个结果都是通过一个通用的框架来证明的，该框架同时捕获了几个定义，直接受到Esparza，Ganty，Leroux和Majumder最近的Petri网结果的启发[CONCUR 2015]。这些结果支持了无错误CRN的计算表达能力是内在的，对任意定义选择不敏感的论点。
We show that some natural output conventions for error-free computation in chemical reaction networks (CRN) lead to a common level of computational expressivity. Our main results are that the standard definition of error-free CRNs have equivalent computational power to 1) asymmetric and 2) democratic CRNs. The former have only "yes" voters, with the interpretation that the CRN's output is yes if any voters are present and no otherwise. The latter define output by majority vote among "yes" and "no" voters.
Both results are proven via a generalized framework that simultaneously captures several definitions, directly inspired by a recent Petri net result of Esparza, Ganty, Leroux, and Majumder [CONCUR 2015]. These results support the thesis that the computational expressivity of error-free CRNs is intrinsic, not sensitive to arbitrary definitional choices.
DOI：
10.1137/1.9781611974782.169
发表时间：
2016-02
期刊：
ArXiv
影响因子：
--
作者：
Dan Alistarh;J. Aspnes;David Eisenstat;Rati Gelashvili;R. Rivest
通讯作者：
Dan Alistarh;J. Aspnes;David Eisenstat;Rati Gelashvili;R. Rivest