On the computational complexity of membrane systems

DOI10.1016/J.TCS.2004.03.045MaRDI QIDQ596128zbMATH OpenOpenAlexFDO

Authors Oscar H. Ibarra

Publication date 10 August 2004

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

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

zbMATH Keywords

AcceptorCatalytic systemCommunicating P systemGeneratorMembrane computingReachabilitySemilinearSpace boundedSymport/antiport systemTime bounded

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Computing with cells: membrane systems – some complexity issues
• Complexity classes for membrane systems
• Complexity classes for membrane systems: a survey
• Computational complexity aspects in membrane computing
• Mathematical Foundations of Computer Science 2003

Cites work

• A guide to membrane computing.
• A Note Concerning Nondeterministic Tape Complexities
• A note on multihead automata and context-sensitive languages
• Computationally universal P systems without priorities: Two catalysts are sufficient
• COMPUTING BY COMMUNICATION IN NETWORKS OF MEMBRANES
• Computing with membranes
• Counter machines and counter languages
• scientific article; zbMATH DE number 5604070 (Why is no real title available?)
• scientific article; zbMATH DE number 1735631 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2003
• Membrane Computing
• Membrane computing. An introduction.
• Membrane computing: When communication is enough
• Membrane systems with symport/antiport rules: Universality results
• On the power of P systems with symport rules
• P automata or purely communicating accepting P systems
• P systems with symport/Antiport rules: The traces of objects
• P systems without priorities are computationally universal
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Relationships between nondeterministic and deterministic tape complexities
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Simulating counter automata by P systems with symport/antiport
• Solving NP-complete problems using P-systems with active membranes
• Some decision problems concerning semilinearity and commutation.
• Tally languages and complexity classes
• The chemical abstract machine
• The power of communication: P systems with symport/antiport
• Turing machines with restricted memory access

Cited in

(16)

• Complexity classes in models of cellular computing with membranes
• On membrane hierarchy in P systems
• Time and space complexity of P systems -- and why they matter
• Selected Topics in Computational Complexity of Membrane Systems
• On the branching complexity of P systems
• ON THE POWER OF DETERMINISTIC AND SEQUENTIAL COMMUNICATING P SYSTEMS
• On Bounded Symport/Antiport P Systems
• P systems with proteins on membranes characterize PSPACE
• Computing with membranes (P systems): Universality results
• On the Computational Power of Flip-Flop Proteins on Membranes
• Mathematical Foundations of Computer Science 2003
• P and dP automata: unconventional versus classical automata
• Non-confluence in divisionless P systems with active membranes
• Cycles and communicating classes in membrane systems and molecular dynamics
• On the computational complexity of P automata
• Reversing computation in membrane systems

This page was built for publication: On the computational complexity of membrane systems

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