P systems with proteins on membranes characterize PSPACE
From MaRDI portal
Publication:388151
DOI10.1016/j.tcs.2013.03.009zbMath1293.68175OpenAlexW2084545956MaRDI QIDQ388151
Alfonso Rodríguez-Patón, Petr Sosík, Andrei Păun
Publication date: 19 December 2013
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2013.03.009
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Protein sequences, DNA sequences (92D20)
Related Items (10)
An efficient time-free solution to SAT problem by P systems with proteins on membranes ⋮ Solving a PSPACE-complete problem by symport/antiport P systems with promoters and membrane division ⋮ An efficient time-free solution to QSAT problem using P systems with proteins on membranes ⋮ Cell-like P systems with evolutional symport/antiport rules and membrane creation ⋮ The computational power of cell-like P systems with one protein on membrane ⋮ P systems with proteins: a new frontier when membrane division disappears ⋮ P systems attacking hard problems beyond NP: a survey ⋮ Rule synchronization for tissue P systems ⋮ Cell-like P systems with polarizations and minimal rules ⋮ Solving the 3-COL problem by using tissue P systems without environment and proteins on cells
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the computational complexity of membrane systems
- The power of communication: P systems with symport/antiport
- Membrane computing and complexity theory: A characterization of PSPACE
- P systems with minimal parallelism
- Membrane systems with proteins embedded in membranes
- (Mem)brane automata
- A new characterization of NP, P, and PSPACE with accepting hybrid networks of evolutionary processors
- Membrane computing with transport and embedded proteins
- The computational power of cell division in P systems: Beating down parallel computers?
- Complexity theory and genetics: The computational power of crossing over
- Tissue P Systems and (Mem)Brane Systems with Mate and Drip Operations Working on Strings
- Computing with Cells
- P Systems with Proteins on Membranes and Membrane Division
- Cell Cycle and Tumor Growth in Membrane Systems with Peripheral Proteins
- On the Computational Power of Flip-Flop Proteins on Membranes
- On Flip-Flop Membrane Systems with Proteins
- A ROBUST DNA COMPUTATION MODEL THAT CAPTURES PSPACE
- Brane Calculi
- A Computational Complexity Theory in Membrane Computing
This page was built for publication: P systems with proteins on membranes characterize PSPACE
