Theory of reaction automata: a survey

Takashi Yokomori, Fumiya Okubo

研究成果: ジャーナルへの寄稿学術誌査読

2 被引用数 (Scopus)

抄録

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.

本文言語英語
ページ(範囲)63-85
ページ数23
ジャーナルJournal of Membrane Computing
3
1
DOI
出版ステータス出版済み - 3月 2021
外部発表はい

!!!All Science Journal Classification (ASJC) codes

  • 計算理論と計算数学
  • 応用数学

フィンガープリント

「Theory of reaction automata: a survey」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル