C-5-57
A Computing Model for Biochemical Reactions
Fumiya Okubo 1f.okubo@akane.waseda.jp

12Takashi Yokomori 2	  	 yokomori@waseda.jp

Graduate School of Education, Waseda University,
1-6-1 Nishiwaseda, Shinjuku-ku, Tokyo 169-8050, Japan
Department of Mathematics, Faculty of Education and Integrated Arts and Sciences,
Waseda University, 1-6-1 Nishiwaseda, Shinjuku-ku, Tokyo 169-8050, Japan

Keywords: Models of biochemical reactions, Reaction automata, Turing computability
Recent developments on the theory of reaction automata ([4,5,6]) are surveyed. In these years,Ehrenfeucht and Rozenberg have introduced a formal model, called reaction systems ([2]), forinvestigating interactions between biochemical reactions. Reaction systems provide a formal
framework suited for investigating at an abstract level the way of biochemical functioning.
Meanwhile, the notion of a multiset has frequently appeared and been investigated in many areasof computer science and related fields ([1,7]) because of its usefulness. In fact, identifying a
volume of compound chemicals as a multiset makes it possible that a multiset rewriting provides anatural way to express chemical reactions. Combining two notions of a reaction system and of amultiset rewriting, we have introduced reaction automata as computing devices for accepting string
languages ([4]), in order to model and analyze the behaviors of biochemical reactions in thecomputational framework.
The notion of reaction automata is an extension of reaction systems in which reaction rules aredefined by triples consisting of reactants, inhibitors, and products. A computation process of areaction automaton is performed in such a way that each time receiving one symbol from an inputstring, a reaction automaton changes its memory (multiset) by applying reaction rules to themultiset. Since reaction automata are a computing model based on multiset rewriting that accepts
string languages, their modeling capability for chemical reactions can be investigated in terms ofthe theory of computation ([3]).
It is shown that reaction automata are computationally Turing universal. Further, Computational
complexity issues for some classes of reaction automata are explored in comparison to language
classes in the Chomsky hierarchy.
[1] C.Calude, Gh. Paun, G. Rozenberg and A. Salomaa (Eds.), Multiset Processing, LNCS 2235, Springer,
2001.
[2] A. Ehrenfeucht, G. Rozenberg, Reaction systems, Fundamenta Informaticae vol.75, pp.263-280, 2007.
[3] J.E. Hopcroft, T. Motwani, J.D. Ullman, Introduction to automata theory, language and computation 2nd ed, Addison-Wesley, 2003.
[4] F. Okubo, On the Computational Power of Reaction Automata Working in Sequential Manner, 4thWorkshop on Non-Classical Models for Automata and Applications, book@ocg.at series 290, pp.149-164,Österreichische Computer Gesellschaft, 2012.
[5] F. Okubo, S. Kobayashi, T. Yokomori, Reaction Automata, Theoretical Computer Science, 429,pp.247-257, 2012.
[6] F. Okubo, S. Kobayashi, T. Yokomori, On the Properties of Language Classes Defined by Bounded
Reaction Automata, Theoretical Computer Science, 454, pp.206-221, 2012.
[7] Y. Suzuki, Y. Fujiwara, J. Takabayashi, H. Tanaka, Artificial Life Applications of a Class of P Systems,in [1], pp.299-346, 2001.