Democratic, existential, and consensus-based output conventions in stable computation by chemical reaction networks
Democratic, existential, and consensus-based output conventions in stable computation by chemical reaction networks
复制标题
化学反应网络稳定计算中民主的、存在的和基于共识的输出约定
DOI：
10.1007/s11047-017-9648-8
复制
发表时间：
2018
影响因子：
2.1
通讯作者：
Soloveichik, David
中科院分区：
文献类型：
--
作者：
Brijder, Robert;Doty, David;Soloveichik, David
我们表明，一些自然的输出公约，在化学反应网络（CRN）的无错误计算导致一个共同的水平的计算表现力。我们的主要结果是，标准的共识为基础的输出约定具有等效的计算能力（1）存在为基础的和（2）民主为基础的输出约定。使用前一种输出约定的CRN只有“是”投票者，其解释是，如果存在任何投票者，则CRN的输出为是，否则为否。使用后一种输出约定的CRN通过“是”和“否”投票者中的多数投票来定义输出。这两个结果都是通过一个通用的框架来证明的，该框架同时捕获了几个定义，直接受到Esparza，Ganty，Leroux和Majumder [CONCUR 2015]的Petri网结果的启发。这些结果支持了无错误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 consensus-based output convention have equivalent computational power to (1)existence-basedand (2)democracy-basedoutput conventions. The CRNs using the former output convention have only “yes” voters, with the interpretation that the CRN’s output is yes if any voters are present and no otherwise. The CRNs using the latter output convention 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 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.
登录
查看更多内容
影响因子：
1.3
作者：
Angluin, Dana;Aspnes, James;Eisenstat, David
通讯作者：
Eisenstat, David
化学反应网络和决策器中的输出稳定性和半线性集
DOI：
--
发表时间：
2014
期刊：
DNA
影响因子：
--
作者：
R. Brijder
通讯作者：
R. Brijder
化学反应网络中表现力的鲁棒性
DOI：
10.1007/978-3-319-43994-5_4
发表时间：
2016
期刊：
ArXiv
影响因子：
--
作者：
R. Brijder;David Doty;D. Soloveichik
通讯作者：
D. Soloveichik
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
无领导的确定性化学反应网络
影响因子：
2.1
作者：
David Doty;Monir Hajiaghayi
通讯作者：
Monir Hajiaghayi