Okubo, F., & Yokomori, T. (2015). Recent developments on reaction automata theory: A survey. In Recent Advances in Natural Computing (pp. 1-22). Springer, Tokyo.
Abstract
This paper surveys recent developments on the theory of reaction automata, which has been lately initiated to model and analyze in the computational framework the behaviors of biochemical reactions in nature. Reaction automata (RAs) have been proposed as computing models for accepting string languages. RAs may be taken as a kind of an extension of reaction systems in that they deal with multisets rather than (usual) sets being dealt with in reaction systems. A computation process by an RA is performed in such a way that after taking in the system an input symbol from the environment, the RA changes its state (represented by a multiset) by applying reaction rules to the multiset in the manner designated, where the maximally parallel manner is considered as well as the (usual) sequential manner. An input sequence of symbols is accepted if the RA stays in a final state (i.e., a designated multiset) at some moment after reading through the input. Thus, RAs may also be regarded as a variant of finite automata in which multisets are used to play a role of (unbounded number of) states. The presented results nclude: RAs have the Turing universal computation power, the computation power of exponential-bounded RAs coincides with that of the linear-bounded Turing machines, the computation power of linear-bounded RAs is incomparable to that of pushdown automata. Further, the case for RAs with sequential mode of rule applications is also investigated.
Okubo, F., & Yokomori, T. (2015). Recent developments on reaction automata theory: A survey. In Recent Advances in Natural Computing (pp. 1-22). Springer, Tokyo.
Abstract This paper surveys recent developments on the theory of reaction automata, which has been lately initiated to model and analyze in the computational framework the behaviors of biochemical reactions in nature. Reaction automata (RAs) have been proposed as computing models for accepting string languages. RAs may be taken as a kind of an extension of reaction systems in that they deal with multisets rather than (usual) sets being dealt with in reaction systems. A computation process by an RA is performed in such a way that after taking in the system an input symbol from the environment, the RA changes its state (represented by a multiset) by applying reaction rules to the multiset in the manner designated, where the maximally parallel manner is considered as well as the (usual) sequential manner. An input sequence of symbols is accepted if the RA stays in a final state (i.e., a designated multiset) at some moment after reading through the input. Thus, RAs may also be regarded as a variant of finite automata in which multisets are used to play a role of (unbounded number of) states. The presented results nclude: RAs have the Turing universal computation power, the computation power of exponential-bounded RAs coincides with that of the linear-bounded Turing machines, the computation power of linear-bounded RAs is incomparable to that of pushdown automata. Further, the case for RAs with sequential mode of rule applications is also investigated.
Link to the online copy
Bibtex file @incollection{okubo2015recent, title={Recent developments on reaction automata theory: A survey}, author={Okubo, Fumiya and Yokomori, Takashi}, booktitle={Recent Advances in Natural Computing}, pages={1--22}, year={2015}, publisher={Springer} }