On the properties of language classes defined by bounded reaction automata

DOI10.1016/J.TCS.2012.03.024MaRDI QIDQ714826zbMATH OpenOpenAlexFDO

Authors Fumiya Okubo, Satoshi Kobayashi, Takashi Yokomori

Publication date 11 October 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.3082

zbMATH Keywords

closure propertyabstract family of languagesbiochemical reaction modelbounded reaction automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Biochemistry, molecular biology (92C40)

Abstract: 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.

Recommendations

• Reaction automata
• Theory of reaction automata: a survey
• Reaction automata working in sequential manner
• Reaction systems made simple. A normal form and a classification theorem
• The computing power of determinism and reversibility in chemical reaction automata

Cites work

• scientific article; zbMATH DE number 3509706 (Why is no real title available?)
• scientific article; zbMATH DE number 1951584 (Why is no real title available?)
• scientific article; zbMATH DE number 2080936 (Why is no real title available?)
• scientific article; zbMATH DE number 2080939 (Why is no real title available?)
• scientific article; zbMATH DE number 2080948 (Why is no real title available?)
• scientific article; zbMATH DE number 5593274 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Characterizations of context-sensitive languages and other language classes in terms of symport/antiport P systems
• Combinatorics of life and death for reaction systems
• Events and modules in reaction systems
• Functions defined by reaction systems
• Introducing time in reaction systems
• Membrane Computing
• Minimization strategies for maximally parallel multiset rewriting systems
• Multiset processing. Mathematical, computer science, and molecular computing points of view
• On the computational complexity of P automata
• P and dP automata: a survey
• Pushdown automata, multiset automata, and Petri nets
• Reaction automata
• Reaction systems

Cited in

(6)

• Reaction automata
• Theory of reaction automata: a survey
• The computing power of determinism and reversibility in chemical reaction automata
• The computational capability of chemical reaction automata
• Decomposition and factorization of chemical reaction transducers
• Reaction automata working in sequential manner

This page was built for publication: On the properties of language classes defined by bounded reaction automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714826)