Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Recent Advances in Natural ComputingRecent Developments on Reaction Automata Theory: A Survey

Recent Advances in Natural Computing: Recent Developments on Reaction Automata Theory: A Survey [This paper surveys recent developments on the theory of reaction automata, which has been lately initiated in [17] 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 are all from [16–18] and include: 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.] http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

Recent Advances in Natural ComputingRecent Developments on Reaction Automata Theory: A Survey

Part of the Mathematics for Industry Book Series (volume 9)
Editors: Suzuki, Yasuhiro; Hagiya, Masami
Okubo, Fumiya; Yokomori, Takashi
Recent Advances in Natural Computing — Jul 30, 2014
Download PDF
22 pages

Loading next page...
 
/lp/springer-journals/recent-advances-in-natural-computing-recent-developments-on-reaction-MwvNn3sFDF
Publisher
Springer Japan
Copyright
© Springer Japan 2015
ISBN
978-4-431-55104-1
Pages
1 –22
DOI
10.1007/978-4-431-55105-8_1
Publisher site
See Chapter on Publisher Site

Abstract

[This paper surveys recent developments on the theory of reaction automata, which has been lately initiated in [17] 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 are all from [16–18] and include: 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.]

Published: Jul 30, 2014

Keywords: Models of biochemical reactions; Reaction automata; Multisets; Chomsky hierarchy; Turing computability

There are no references for this article.