The Computing Power of Determinism and Reversibility in Chemical Reaction Automata
The Computing Power of Determinism and Reversibility in Chemical Reaction Automata
复制标题
DOI：
10.1007/978-3-319-73216-9_13
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Fumiya Okubo;T. Yokomori
中科院分区：
文献类型：
--
作者：
Fumiya Okubo;T. Yokomori
化学反应自动机（CRAs）是Okubo， Yokomori, （DNA20， LNCS, vol. 8727, pp. 53-66,(2014),[25]）引入的基于多集重写的多集存储计算模型。一个CRA由一组有限的反应（或分别称为反应物和生成物的多集对）、一个初始多集和一组最终多集组成。在当前配置（multiset）中获取输入符号，CRA将其更改为新配置。因此，CRA提供了一种类似自动机的计算模型来研究化学反应的计算分析。另一方面，由于Bennett， (IBM J Res Dev, 17（6), 525-532,(1973),[4]）证明了任何（不可逆）图灵机都可以被可逆图灵机有效地模拟，可逆计算已经成为一个越来越受到关注的研究领域。在本文中，我们将决定论和可逆性的概念引入到cra中，并与乔姆斯基层次结构的语言类进行了比较，研究了这些cra类的计算能力。可逆cra的计算能力涉及化学反应网络分子编程的物理实现（Thachuk, Condon, DNA 18， LNCS, vol. 7433, pp. 135-149,(2012),[32]）和DNA链位移系统的实现（Qian, Winfree, Science, 332, 1196-1201,(2011),[32]），因此，从分子计算的理论角度阐明确定性cra和可逆cra的计算能力具有重要意义。
Chemical reaction automata (CRAs) are computing models with multiset storage based on multiset rewriting introduced in Okubo, Yokomori, (DNA20, LNCS, vol. 8727, pp. 53–66, (2014), [25]). A CRA consists of a finite set of reactions (or pairs of multisets called reactants and products, respectively) and an initial multiset as well as a set of final multisets. Taking an input symbol in the current configuration (multiset) a CRA changes it into a new configuration. Thus, a CRA offers an automaton-like computing model to investigate the computational analysis of chemical reactions. On the other hand, since any (irreversible) Turing machine was proven to be effectively simulated by a reversible Turing machine in Bennett, (IBM J Res Dev, 17(6), 525–532, (1973), [4]), reversible computing has become a research field that has been receiving increased attention. In this paper we introduce the notions of determinism and reversibility into CRAs, and investigate the computational powers of those classes of CRAs in comparison with the language classes of Chomsky hierarchy. The computing power of reversible CRAs involves the physical realization of molecular programming of chemical reaction networks (Thachuk, Condon, DNA 18, LNCS, vol. 7433, pp. 135–149, (2012), [32]) with DNA strand displacement system implementation (Qian, Winfree, Science, 332, 1196–1201, (2011), [29]), and therefore, it is of great significance to elucidate the computing capabilities of both deterministic and reversible CRAs from the theoretical viewpoint of molecular computing.