On the computational complexity of membrane systems

DOI10.1016/J.TCS.2004.03.045zbMATH Open1068.68060OpenAlexW2119227111MaRDI QIDQ596128FDOQ596128

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

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

zbMATH Keywords

AcceptorCatalytic systemCommunicating P systemGeneratorMembrane computingReachabilitySemilinearSpace boundedSymport/antiport systemTime bounded

Mathematics Subject Classification ID

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

Cites Work

• Computing with membranes
• Membrane computing. An introduction.
• Computationally universal P systems without priorities: Two catalysts are sufficient
• Some decision problems concerning semilinearity and commutation.
• Relationships between nondeterministic and deterministic tape complexities
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• The power of communication: P systems with symport/antiport
• The chemical abstract machine
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Mathematical Foundations of Computer Science 2003
• Title not available (Why is that?)
• A guide to membrane computing.
• Title not available (Why is that?)
• Counter machines and counter languages
• Membrane Computing
• Turing machines with restricted memory access
• Title not available (Why is that?)
• Title not available (Why is that?)
• P systems with symport/Antiport rules: The traces of objects
• Tally languages and complexity classes
• A note on multihead automata and context-sensitive languages
• COMPUTING BY COMMUNICATION IN NETWORKS OF MEMBRANES
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the power of P systems with symport rules
• A Note Concerning Nondeterministic Tape Complexities

Cited In (16)

• ON THE POWER OF DETERMINISTIC AND SEQUENTIAL COMMUNICATING P SYSTEMS
• Title not available (Why is that?)
• On membrane hierarchy in P systems
• Time and space complexity of P systems -- and why they matter
• 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)