P systems with proteins on membranes characterize PSPACE
From MaRDI portal
Publication:388151
DOI10.1016/j.tcs.2013.03.009zbMath1293.68175MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
92D20: Protein sequences, DNA sequences
Related Items
An efficient time-free solution to SAT problem by P systems with proteins on membranes, Solving the 3-COL problem by using tissue P systems without environment and proteins on cells, The computational power of cell-like P systems with one protein on membrane, Rule synchronization for tissue P systems, Solving a PSPACE-complete problem by symport/antiport P systems with promoters and membrane division, Cell-like P systems with evolutional symport/antiport rules and membrane creation, P systems with proteins: a new frontier when membrane division disappears, P systems attacking hard problems beyond NP: a survey, Cell-like P systems with polarizations and minimal rules, An efficient time-free solution to QSAT problem using P systems with proteins on membranes
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