Computationally universal P systems without priorities: Two catalysts are sufficient

DOI10.1016/j.tcs.2004.06.029zbMath1078.68036OpenAlexW2115404543WikidataQ56485418 ScholiaQ56485418MaRDI QIDQ1763714

Marion Oswald, Rudolf Freund, Petr Sosík, Lila Kari

Publication date: 22 February 2005

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

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

zbMATH Keywords

ComplexityUniversalityP systemsMembrane computingCatalysts

Mathematics Subject Classification ID

Related Items (37)

Small (purely) catalytic P systems simulating register machines ⋮ Properties of Membrane Systems ⋮ P Systems with Chained Rules ⋮ Catalytic P systems, semilinear sets, and vector addition systems ⋮ Variants of derivation modes for which purely catalytic P systems are computationally complete ⋮ Priorities, Promoters and Inhibitors in Deterministic Non-cooperative P Systems ⋮ P Systems with Toxic Objects ⋮ Promoters and Inhibitors in Purely Catalytic P Systems ⋮ When catalytic P systems with one catalyst can be computationally complete ⋮ Variants of derivation modes for which catalytic P systems with one catalyst are computationally complete ⋮ Deterministic catalytic systems are not universal ⋮ On the computational complexity of membrane systems ⋮ Using well-structured transition systems to decide divergence for catalytic P systems ⋮ The power of synchronizing rules in membrane computing ⋮ Towards bridging two cell-inspired models: P systems and R systems ⋮ Morphogenetic computing: computability and complexity results ⋮ Computing with cells: membrane systems – some complexity issues ⋮ The Expressiveness of Concentration Controlled P Systems ⋮ Catalytic and communicating Petri nets are Turing complete ⋮ ON ONE-MEMBRANE P SYSTEMS OPERATING IN SEQUENTIAL MODE ⋮ From P systems to morphogenetic systems: an overview and open problems ⋮ P systems with limited number of objects ⋮ Division rules for tissue P systems inspired by space filling curves ⋮ How derivation modes and halting conditions may influence the computational power of P systems ⋮ Synchronization of rules in membrane computing ⋮ Computational power of tissue P systems for generating control languages ⋮ Computationally universal P systems without priorities: Two catalysts are sufficient ⋮ (Tissue) P systems working in the \(k\)-restricted minimally or maximally parallel transition mode ⋮ On Bounded Symport/Antiport P Systems ⋮ P Systems with Anti-Matter ⋮ P SYSTEMS AND TOPOLOGY: SOME SUGGESTIONS FOR RESEARCH ⋮ FURTHER RESULTS ON TIME-FREE P SYSTEMS ⋮ Rule synchronization for tissue P systems ⋮ On the universality of purely catalytic P systems ⋮ Membrane automata for modeling biomolecular processes ⋮ PARTIAL HALTING IN P SYSTEMS ⋮ On determinism versus nondeterminism in P systems

Cites Work

• The power of catalysts and priorities in membrane systems
• Computing with membranes
• Computationally universal P systems without priorities: Two catalysts are sufficient
• Membrane computing. An introduction.
• From regulated rewriting to computing with membranes: collapsing hierarchies
• Mathematical Foundations of Computer Science 2003
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Computationally universal P systems without priorities: Two catalysts are sufficient