Deterministic catalytic systems are not universal

DOI10.1016/J.TCS.2006.07.029MaRDI QIDQ860859zbMATH OpenOpenAlexFDO

Authors Oscar H. Ibarra, Hsu-Chun Yen

Publication date 9 January 2007

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

Full work available at URL https://doi.org/10.1016/j.tcs.2006.07.029

zbMATH Keywords

membrane computingprioritysemilinear setcounter machinedeterministic catalytic systemdeterministic versus nondeterministicsymport/antiport system

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Grammars and rewriting systems (68Q42)

Recommendations

• Implementation and Application of Automata
• Catalytic P systems, semilinear sets, and vector addition systems
• Membrane Computing
• Computing and Combinatorics
• On the universality of purely catalytic P systems

Cites work

• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• A guide to membrane computing.
• Computationally universal P systems without priorities: Two catalysts are sufficient
• Computing with membranes
• Developments in Language Theory
• Membrane computing. An introduction.
• On the analysis of Petri nets with static priorities
• The power of communication: P systems with symport/antiport

Cited in

(10)

• Using well-structured transition systems to decide divergence for catalytic P systems
• Catalytic P systems, semilinear sets, and vector addition systems
• Promoters and inhibitors in purely catalytic P systems
• Membrane Computing
• Properties of membrane systems
• Mathematical Foundations of Computer Science 2003
• Priorities, promoters and inhibitors in deterministic non-cooperative P systems
• scientific article; zbMATH DE number 6829365 (Why is no real title available?)
• Implementation and Application of Automata
• P systems and topology: some suggestions for research

This page was built for publication: Deterministic catalytic systems are not universal

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