TY - JOUR
T1 - Reaction automata
AU - Okubo, Fumiya
AU - Kobayashi, Satoshi
AU - Yokomori, Takashi
N1 - Funding Information:
The authors gratefully acknowledge useful remarks and comments by anonymous referees which improved an earlier version of this paper. The work of F. Okubo was possible due to Waseda University Grant for Special Research Projects: 2011A-842. The work of S. Kobayashi was in part supported by Grants-in-Aid for Scientific Research (C) No.22500010, Japanese Society for the Promotion of Science. The work of T. Yokomori was in part supported by Waseda University Grant for Special Research Projects: 2011B-056.
PY - 2012/4/20
Y1 - 2012/4/20
N2 - Reaction systems are a formal model that has been introduced to investigate the interactive behaviors of biochemical reactions. Based on the formal framework of reaction systems, we propose new computing models called reaction automata that feature (string) language acceptors with multiset manipulation as a computing mechanism, and show that reaction automata are computationally Turing universal. Further, some subclasses of reaction automata with space complexity are investigated and their language classes are compared to the ones in the Chomsky hierarchy.
AB - Reaction systems are a formal model that has been introduced to investigate the interactive behaviors of biochemical reactions. Based on the formal framework of reaction systems, we propose new computing models called reaction automata that feature (string) language acceptors with multiset manipulation as a computing mechanism, and show that reaction automata are computationally Turing universal. Further, some subclasses of reaction automata with space complexity are investigated and their language classes are compared to the ones in the Chomsky hierarchy.
KW - Models of biochemical reactions
KW - Reaction automata
KW - Turing computability
UR - http://www.scopus.com/inward/record.url?scp=84858335042&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84858335042&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2011.12.045
DO - 10.1016/j.tcs.2011.12.045
M3 - Article
AN - SCOPUS:84858335042
SN - 0304-3975
VL - 429
SP - 247
EP - 257
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -