On the Properties of Language Classes Defined by Bounded Reaction Automata

Details On the Properties of Language Classes Defined by Bounded Reaction Automata On the Properties of Language Classes Defined by Bounded Reaction Automata

2012-01-15

arxiv.org/abs/1201.3082v1

Computer Science

Formal Languages and Automata Theory

23 pages with 3 figures

Scientific paper

Reaction automata are a formal model that has been introduced to investigate the computing powers of interactive behaviors of biochemical reactions([14]). Reaction automata are language acceptors with multiset rewriting mechanism whose basic frameworks are based on reaction systems introduced in [4]. 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 linearbounded reaction automata (LRAs) and exponentially-bounded reaction automata (ERAs). Besides LRAs, we newly introduce an extended model (denoted by lambda-LRAs) by allowing lambda-moves in the accepting process of reaction, and investigate the closure properties of language classes accepted by both LRAs and lambda-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 lambda-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.

Affiliated with

Also associated with

No associations

Rating

On the Properties of Language Classes Defined by Bounded Reaction Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Properties of Language Classes Defined by Bounded Reaction Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Properties of Language Classes Defined by Bounded Reaction Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-159242