Reaction automata

DOI10.1016/J.TCS.2011.12.045MaRDI QIDQ418799zbMATH OpenOpenAlexFDO

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

models of biochemical reactionsreaction automataTuring computability

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

• 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
• 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?)
• 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

(17)

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