Catalytic P systems, semilinear sets, and vector addition systems

DOI10.1016/j.tcs.2003.10.028zbMath1070.68043OpenAlexW2154099358MaRDI QIDQ1884955

Ömer Eğecioğlu, Oscar H. Ibarra, Zhe Dang

Publication date: 27 October 2004

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

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

zbMATH Keywords

Catalytic systemMembrane computingReachability problemSemilinear setVector addition system

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items

Small (purely) catalytic P systems simulating register machines, Computation in networks of passively mobile finite-state sensors, On the verification of membrane systems with dynamic structure, On stateless deterministic restarting automata, The computational power of enzymatic numerical P systems working in the sequential mode, Computation power of asynchronous spiking neural P systems with polarizations, On the teaching complexity of linear sets, The computational power of population protocols, ON STATELESS AUTOMATA AND P SYSTEMS, A Biologically Inspired Model with Fusion and Clonation of Membranes, Division rules for tissue P systems inspired by space filling curves, On membrane hierarchy in P systems, On Stateless Deterministic Restarting Automata, On the Dynamics of PB Systems with Volatile Membranes, ON VARIOUS NOTIONS OF PARALLELISM IN P SYSTEMS, On the universality of purely catalytic P systems, Membrane automata for modeling biomolecular processes, On the Teaching Complexity of Linear Sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Persistence of vector replacement systems is decidable
• On the reachability problem for 5-dimensional vector addition systems
• The chemical abstract machine
• The equality problem for vector addition systems is undecidable
• Membrane systems with promoters/inhibitors
• Computing with membranes
• Computationally universal P systems without priorities: Two catalysts are sufficient
• A guide to membrane computing.
• Membrane computing. An introduction.
• Commutative grammars: The complexity of uniform word problems
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Petri nets, commutative context-free grammars, and basic parallel processes
• COMPUTING WITH MEMBRANES (P SYSTEMS): A VARIANT
• On Context-Free Languages