On the properties of language classes defined by bounded reaction automata

DOI10.1016/J.TCS.2012.03.024zbMATH Open1252.68180arXiv1201.3082OpenAlexW2081383229MaRDI QIDQ714826FDOQ714826

Authors: Fumiya Okubo, Satoshi Kobayashi, Takashi Yokomori 

Publication date: 11 October 2012

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

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.

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

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

zbMATH Keywords

closure propertyabstract family of languagesbiochemical reaction modelbounded reaction automata

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Introducing time in reaction systems
• Functions defined by reaction systems
• Reaction systems
• Events and modules in reaction systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multiset processing. Mathematical, computer science, and molecular computing points of view
• Title not available (Why is that?)
• Reaction automata
• P and dP automata: a survey
• Combinatorics of life and death for reaction systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Pushdown automata, multiset automata, and Petri nets
• Minimization strategies for maximally parallel multiset rewriting systems
• Membrane Computing
• Characterizations of context-sensitive languages and other language classes in terms of symport/antiport P systems
• On the computational complexity of P automata

Cited In (6)

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

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)