Membrane computing and complexity theory: A characterization of PSPACE
From MaRDI portal
Publication:859989
DOI10.1016/j.jcss.2006.10.001zbMath1178.68260OpenAlexW2085484366MaRDI QIDQ859989
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
Related Items (33)
P Systems Simulating Oracle Computations ⋮ Non-confluence in divisionless P systems with active membranes ⋮ On the power of P systems with active membranes using weak non-elementary membrane division ⋮ Characterising the complexity of tissue P systems with fission rules ⋮ P systems with proteins on membranes characterize PSPACE ⋮ The counting power of P systems with antimatter ⋮ Reaching efficiency through collaboration in membrane systems: dissolution, polarization and cooperation ⋮ On the power of membrane dissolution in polarizationless P systems with active membranes ⋮ Shallow Non-confluent P Systems ⋮ Space complexity equivalence of P systems with active membranes and Turing machines ⋮ Computing with cells: membrane systems – some complexity issues ⋮ Cell-like P systems with evolutional symport/antiport rules and membrane creation ⋮ A limitation of cell division in tissue P systems by PSPACE ⋮ A Characterisation of NL Using Membrane Systems without Charges and Dissolution ⋮ A Turing machine simulation by P systems without charges ⋮ Bounding the space in P systems with active membranes ⋮ Simulating counting oracles with cooperation ⋮ Seeking computational efficiency boundaries: the Păun's conjecture ⋮ A new method to simulate restricted variants of polarizationless P systems with active membranes ⋮ Selected Topics in Computational Complexity of Membrane Systems ⋮ RESEARCH FRONTIERS OF MEMBRANE COMPUTING: OPEN PROBLEMS AND RESEARCH TOPICS ⋮ The computational power of membrane systems under tight uniformity conditions ⋮ Subroutines in P systems and closure properties of their complexity classes ⋮ When object production tunes the efficiency of membrane systems ⋮ Active Membrane Systems Without Charges and Using Only Symmetric Elementary Division Characterise P ⋮ P SYSTEMS WITH PROTEINS ON MEMBRANES: A SURVEY ⋮ Characterizing PSPACE with shallow non-confluent P systems ⋮ P systems attacking hard problems beyond NP: a survey ⋮ Rule synchronization for tissue P systems ⋮ Cell-like P systems with polarizations and minimal rules ⋮ Optical computing ⋮ Depth-two P systems can simulate Turing machines with \textbf{NP} oracles ⋮ P systems with evolutional symport and membrane creation rules solving QSAT
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tissue P systems.
- Complexity classes in models of cellular computing with membranes
- The computational power of cell division in P systems: Beating down parallel computers?
- Computing with membranes
- Complexity theory and genetics: The computational power of crossing over
- Membrane computing. An introduction.
- Simulating quadratic dynamical systems is PSPACE-complete (preliminary version)
- Complexity classes for membrane systems
- A ROBUST DNA COMPUTATION MODEL THAT CAPTURES PSPACE
- Membrane Computing
This page was built for publication: Membrane computing and complexity theory: A characterization of PSPACE
