Membrane computing and complexity theory: A characterization of PSPACE
From MaRDI portal
Publication:859989
DOI10.1016/J.JCSS.2006.10.001zbMATH Open1178.68260OpenAlexW2085484366MaRDI QIDQ859989FDOQ859989
Alfonso Rodríguez-Patón, Petr Sosík
Publication date: 22 January 2007
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2006.10.001
Recommendations
Cites Work
- Computing with membranes
- Membrane computing. An introduction.
- Tissue P systems.
- Title not available (Why is that?)
- The computational power of cell division in P systems: Beating down parallel computers?
- Complexity theory and genetics: The computational power of crossing over
- P systems with active membranes: Attacking NP-complete problems
- Title not available (Why is that?)
- A ROBUST DNA COMPUTATION MODEL THAT CAPTURES PSPACE
- Title not available (Why is that?)
- Complexity classes in models of cellular computing with membranes
- Membrane Computing
- Simulating quadratic dynamical systems is PSPACE-complete (preliminary version)
- Complexity classes for membrane systems
Cited In (35)
- A Turing machine simulation by P systems without charges
- Bounding the space in P systems with active membranes
- Simulating counting oracles with cooperation
- Title not available (Why is that?)
- Characterizing PSPACE with shallow non-confluent P systems
- P systems attacking hard problems beyond NP: a survey
- P Systems Simulating Oracle Computations
- Subroutines in P systems and closure properties of their complexity classes
- Non-confluence in divisionless P systems with active membranes
- Optical computing
- The computational power of membrane systems under tight uniformity conditions
- On maximal parallel application of rules in rewriting P systems
- On the power of membrane dissolution in polarizationless P systems with active membranes
- Shallow Non-confluent P Systems
- P SYSTEMS WITH PROTEINS ON MEMBRANES: A SURVEY
- Seeking computational efficiency boundaries: the Păun's conjecture
- P systems with proteins on membranes characterize PSPACE
- A Characterisation of NL Using Membrane Systems without Charges and Dissolution
- Rule synchronization for tissue P systems
- Cell-like P systems with evolutional symport/antiport rules and membrane creation
- Space complexity equivalence of P systems with active membranes and Turing machines
- A new method to simulate restricted variants of polarizationless P systems with active membranes
- On the power of P systems with active membranes using weak non-elementary membrane division
- Cell-like P systems with polarizations and minimal rules
- Characterising the complexity of tissue P systems with fission rules
- A limitation of cell division in tissue P systems by PSPACE
- RESEARCH FRONTIERS OF MEMBRANE COMPUTING: OPEN PROBLEMS AND RESEARCH TOPICS
- When object production tunes the efficiency of membrane systems
- Active Membrane Systems Without Charges and Using Only Symmetric Elementary Division Characterise P
- Reaching efficiency through collaboration in membrane systems: dissolution, polarization and cooperation
- The counting power of P systems with antimatter
- Computing with cells: membrane systems – some complexity issues
- Depth-two P systems can simulate Turing machines with \textbf{NP} oracles
- P systems with evolutional symport and membrane creation rules solving QSAT
- Selected Topics in Computational Complexity of Membrane Systems
This page was built for publication: Membrane computing and complexity theory: A characterization of PSPACE
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q859989)
