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

• scientific article; zbMATH DE number 1583885 (Why is no real title available?)
• 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 1951584 (Why is no real title available?)
• scientific article; zbMATH DE number 1951588 (Why is no real title available?)
• scientific article; zbMATH DE number 1951589 (Why is no real title available?)
• scientific article; zbMATH DE number 1951598 (Why is no real title available?)
• scientific article; zbMATH DE number 2013814 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• A Note Concerning Nondeterministic Tape Complexities
• A guide to membrane computing.
• A note on multihead automata and context-sensitive languages
• COMPUTING BY COMMUNICATION IN NETWORKS OF MEMBRANES
• Computationally universal P systems without priorities: Two catalysts are sufficient
• Computing with membranes
• Counter machines and counter languages
• Mathematical Foundations of Computer Science 2003
• Membrane Computing
• Membrane computing. An introduction.
• On the power of P systems with symport rules
• P systems with symport/Antiport rules: The traces of objects
• 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
• 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)

• ON THE POWER OF DETERMINISTIC AND SEQUENTIAL COMMUNICATING P SYSTEMS
• On membrane hierarchy in P systems
• Time and space complexity of P systems -- and why they matter
• scientific article; zbMATH DE number 1738655 (Why is no real title available?)
• Reversing computation in membrane systems
• 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
• P systems with proteins on membranes characterize PSPACE
• On the Computational Power of Flip-Flop Proteins on Membranes
• Complexity classes in models of cellular computing with membranes
• On the branching complexity of \(P\) systems
• P and dP automata: unconventional versus classical automata
• Mathematical Foundations of Computer Science 2003
• On Bounded Symport/Antiport P Systems
• Selected Topics in Computational Complexity of 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)