Reaction automata

DOI10.1016/J.TCS.2011.12.045MaRDI QIDQ418799zbMATHOpenAlexFDO

Authors Fumiya Okubo, Satoshi Kobayashi, Takashi Yokomori

Publication date 30 May 2012

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

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

zbMATH Keywords

Turing computabilitymodels of biochemical reactionsreaction automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: Reaction systems are a formal model that has been introduced to investigate the interactive behaviors of biochemical reactions. Based on the formal framework of reaction systems, we propose new computing models called reaction automata that feature (string) language acceptors with multiset manipulation as a computing mechanism, and show that reaction automata are computationally Turing universal. Further, some subclasses of reaction automata with space complexity are investigated and their language classes are compared to the ones in the Chomsky hierarchy.

Recommendations

• Theory of reaction automata: a survey
• On the properties of language classes defined by bounded reaction automata
• Reaction systems
• Reaction systems: a model of computation inspired by the functioning of the living cell
• Reaction systems made simple. A normal form and a classification theorem

Cites work

• scientific article; zbMATH DE number 5671765 (Why is no real title available?)
• scientific article; zbMATH DE number 193524 (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 5593273 (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?)
• A variant of random context grammars: Semi-conditional grammars
• Combinatorics of life and death for reaction systems
• Computation with finite stochastic chemical reaction networks
• Computing with membranes
• Events and modules in reaction systems
• Functions defined by reaction systems
• Introducing time in reaction systems
• Minimization strategies for maximally parallel multiset rewriting systems
• Multiset processing. Mathematical, computer science, and molecular computing points of view
• P and dP automata: a survey
• Pushdown automata, multiset automata, and Petri nets
• Reaction systems
• Spiking neural dP systems

Cited in

(15)

• Reactive Turing machines
• Reaction automata working in sequential manner
• Decomposition and factorization of chemical reaction transducers
• The computational capability of chemical reaction automata
• Reaction systems made simple. A normal form and a classification theorem
• Theory of reaction automata: a survey
• Bag automata and stochastic retrieval of biomolecules in solution
• scientific article; zbMATH DE number 2111976 (Why is no real title available?)
• Model checking temporal properties of reaction systems
• Minimal reaction systems revisited and reaction system rank
• On the properties of language classes defined by bounded reaction automata
• On the computational power of swarm automata using agents with position information
• Design of reactive algorithms by solving equations over automata
• The computational capability of chemical reaction automata
• The computing power of determinism and reversibility in chemical reaction automata

This page was built for publication: Reaction automata

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