2012/01/15 by Fumiya Okubo, Okubo, Fumiya, Satoshi Kobayashi +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #68Q45 (Primary) 68Q05 (Secondary) #Chemical Synthesis and Analysis #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL #msc:68Q05 #msc:68Q45 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1201.3082
23 pages with 3 figures
arxiv created 2012/01/15 · openalex publication_date 2012/01/15 · arxiv updated 2012/01/17 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
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.