The Computing Power of Determinism and Reversibility in Chemical Reaction Automata

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.