On the properties of language classes defined by bounded reaction automata

Fumiya Okubo, Satoshi Kobayashi, Takashi Yokomori*


研究成果: Article査読

9 被引用数 (Scopus)


Reaction automata are a formal model that has been introduced to investigate the computing powers of interactive behaviors of biochemical reactions (Okubo et al. (2012) [19]). Reaction automata are language acceptors with multiset rewriting mechanism whose basic frameworks are based on reaction systems introduced in Ehrenfeucht and Rozenberg (2007) [8]. In this paper we continue the investigation of reaction automata with a focus on the formal language theoretic properties of subclasses of reaction automata, called linear-bounded reaction automata (LRAs) and exponentially-bounded reaction automata (ERAs). Besides LRAs, we newly introduce an extended model (denoted by λ-LRAs) by allowing λ-moves in the accepting process of reaction, and investigate the closure properties of language classes accepted by both LRAs and λ-LRAs. Further, we establish new relationships of language classes accepted by LRAs and by ERAs with the Chomsky hierarchy. The main results include the following: the class of languages accepted by λ-LRAs forms an AFL with additional closure properties,any recursively enumerable language can be expressed as a homomorphic image of a language accepted by an LRA,the class of languages accepted by ERAs coincides with the class of context-sensitive languages.

ジャーナルTheoretical Computer Science
出版ステータスPublished - 2012 10月 5

ASJC Scopus subject areas

  • 理論的コンピュータサイエンス
  • コンピュータ サイエンス(全般)


「On the properties of language classes defined by bounded reaction automata」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。