TY - JOUR

T1 - Theory of reaction automata

T2 - a survey

AU - Yokomori, Takashi

AU - Okubo, Fumiya

N1 - Funding Information:
The work of T. Yokomori was in part supported by JSPS KAKENHI, Grant-in-Aid for Scientific Research (C) JP17K00021. The work of F. Okubo was in part supported by Grants-in-Aid for Young Scientists (B) No. 24700304, Japan Society for the Promotion of Science.
Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Nature Singapore Pte Ltd. part of Springer Nature.

PY - 2021/3

Y1 - 2021/3

N2 - In this paper, we survey on reaction automata theory to model and analyze the biochemical behaviors of vital reactions occurring in nature. Inspired by two notions of a reaction system initiated by Ehrenfeucht and Rozenberg in 2007 and of a multiset, reaction automata (RAs) have been proposed as computing models for accepting string languages. Given an input sequence of symbols, an RA performs its computation process as follows: at every time of receiving an input symbol, it changes the current configuration (represented by a multiset) by applying reaction rules to the multiset in a prescribed manner, for which two kinds of application manners are considered: the maximally parallel manner and the (usual) sequential manner. An RA functions as an extended finite automaton in which multisets play a role of (unbounded number of) states and the state transition is performed by applying reaction rules. We show that the computational powers of RAs are Turing universal in both manners of rule applications. The relationship between the space-bounded variants of RA and the Chomsky hierarchy is also discussed. Further, we discuss the notion of chemical reaction automata, which is a simplified variant of RAs with reaction rules that are free from inhibitor functioning. We complete this survey with a variety of related models of computing together with future research topics.

AB - In this paper, we survey on reaction automata theory to model and analyze the biochemical behaviors of vital reactions occurring in nature. Inspired by two notions of a reaction system initiated by Ehrenfeucht and Rozenberg in 2007 and of a multiset, reaction automata (RAs) have been proposed as computing models for accepting string languages. Given an input sequence of symbols, an RA performs its computation process as follows: at every time of receiving an input symbol, it changes the current configuration (represented by a multiset) by applying reaction rules to the multiset in a prescribed manner, for which two kinds of application manners are considered: the maximally parallel manner and the (usual) sequential manner. An RA functions as an extended finite automaton in which multisets play a role of (unbounded number of) states and the state transition is performed by applying reaction rules. We show that the computational powers of RAs are Turing universal in both manners of rule applications. The relationship between the space-bounded variants of RA and the Chomsky hierarchy is also discussed. Further, we discuss the notion of chemical reaction automata, which is a simplified variant of RAs with reaction rules that are free from inhibitor functioning. We complete this survey with a variety of related models of computing together with future research topics.

UR - http://www.scopus.com/inward/record.url?scp=85107870578&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85107870578&partnerID=8YFLogxK

U2 - 10.1007/s41965-021-00070-6

DO - 10.1007/s41965-021-00070-6

M3 - Article

AN - SCOPUS:85107870578

SN - 2523-8906

VL - 3

SP - 63

EP - 85

JO - Journal of Membrane Computing

JF - Journal of Membrane Computing

IS - 1

ER -