Okubo, F., Kobayashi, S., & Yokomori, T. (2012). On the properties of language classes defined by bounded reaction automata. Theoretical Computer Science, 454, 206-221.Abstract
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) ). Reaction automata are language acceptors with multiset rewriting mechanism whose basic frameworks are based on reaction systems introduced in Ehrenfeucht and Rozenberg (2007) .
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:
(i)
the class of languages accepted by
-LRAs forms an AFL with additional closure properties,
(ii)
any recursively enumerable language can be expressed as a homomorphic image of a language accepted by an LRA,
(iii)
the class of languages accepted by ERAs coincides with the class of context-sensitive languages.
@article{okubo2012properties,
title={On the properties of language classes defined by bounded reaction automata},
author={Okubo, Fumiya and Kobayashi, Satoshi and Yokomori, Takashi},
journal={Theoretical Computer Science},
volume={454},
pages={206--221},
year={2012},
publisher={Elsevier}
}
Okubo, F., Kobayashi, S., & Yokomori, T. (2012). On the properties of language classes defined by bounded reaction automata. Theoretical Computer Science, 454, 206-221. Abstract 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) ). Reaction automata are language acceptors with multiset rewriting mechanism whose basic frameworks are based on reaction systems introduced in Ehrenfeucht and Rozenberg (2007) .
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: (i) the class of languages accepted by -LRAs forms an AFL with additional closure properties,
(ii) any recursively enumerable language can be expressed as a homomorphic image of a language accepted by an LRA,
(iii) the class of languages accepted by ERAs coincides with the class of context-sensitive languages.
Link to the online copy
Bibtex file
@article{okubo2012properties, title={On the properties of language classes defined by bounded reaction automata}, author={Okubo, Fumiya and Kobayashi, Satoshi and Yokomori, Takashi}, journal={Theoretical Computer Science}, volume={454}, pages={206--221}, year={2012}, publisher={Elsevier} }