Complexity classes in models of cellular computing with membranes
From MaRDI portal
Publication:1410766
zbMath1048.68043MaRDI QIDQ1410766
Fernando Sancho Caparrini, Álvaro Romero-Jiménez, Mario J. Pérez-Jiménez
Publication date: 15 October 2003
Published in: Natural Computing (Search for Journal in Brave)
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (58)
Formal Verification of P Systems with Active Membranes through Model Checking ⋮ P Systems Simulating Oracle Computations ⋮ Non-confluence in divisionless P systems with active membranes ⋮ From distribution to replication in cooperative systems with active membranes: a frontier of the efficiency ⋮ On the power of P systems with active membranes using weak non-elementary membrane division ⋮ Membrane computing and complexity theory: A characterization of PSPACE ⋮ Efficient simulation of tissue-like P systems by transition cell-like P systems ⋮ On the efficiency of cell-like and tissue-like recognizing membrane systems ⋮ Solving SAT with P systems with anti-membranes ⋮ Nondeterministic seedless oritatami systems and hardness of testing their equivalence ⋮ A path to computational efficiency through membrane computing ⋮ Membrane fission versus cell division: when membrane proliferation is not enough ⋮ The power of synchronizing rules in membrane computing ⋮ On the efficiency of synchronized P systems ⋮ From \texttt{SAT} to \texttt{SAT}-\texttt{UNSAT} using P systems with dissolution rules ⋮ A bibliometric analysis of membrane computing (1998--2019) ⋮ Asynchronous P systems with active membranes ⋮ Membrane creation and symport/antiport rules solving QSAT ⋮ Tissue P systems with evolutional communication rules with two objects in the left-hand side ⋮ From NP-completeness to DP-completeness: a membrane computing perspective ⋮ Remarks on the Computational Power of Some Restricted Variants of P Systems with Active Membranes ⋮ Shallow Non-confluent P Systems ⋮ Space complexity equivalence of P systems with active membranes and Turing machines ⋮ Cell-like P systems with evolutional symport/antiport rules and membrane creation ⋮ The computational complexity of tissue P systems with evolutional symport/antiport rules ⋮ TISSUE-LIKE P SYSTEMS WITH DYNAMICALLY EMERGING REQUESTS ⋮ A limitation of cell division in tissue P systems by PSPACE ⋮ A Characterisation of NL Using Membrane Systems without Charges and Dissolution ⋮ Seeking computational efficiency boundaries: the Păun's conjecture ⋮ From P systems to morphogenetic systems: an overview and open problems ⋮ 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 ⋮ A toolbox for simpler active membrane algorithms ⋮ The computational power of membrane systems under tight uniformity conditions ⋮ A uniform solution to the independent set problem through tissue P systems with cell separation ⋮ Trading polarizations for labels in P systems with active membranes ⋮ Solving the subset-problem by P systems with active membrans ⋮ Solving PP-Complete and #P-Complete Problems by P Systems with Active Membranes ⋮ Simulating a P system based efficient solution to SAT by using GPUs ⋮ A P-Lingua based simulator for tissue P systems ⋮ Solving HPP and SAT by P systems with active membranes and separation rules ⋮ A $\Sigma_2^P \cup \Pi_2^P$ Lower Bound Using Mobile Membranes ⋮ Subroutines in P systems and closure properties of their complexity classes ⋮ P systems with symport/antiport rules: when do the surroundings matter? ⋮ When object production tunes the efficiency of membrane systems ⋮ Active Membrane Systems Without Charges and Using Only Symmetric Elementary Division Characterise P ⋮ ON A PARTIAL AFFIRMATIVE ANSWER FOR A PĂUN'S CONJECTURE ⋮ PSYSTEMS WITH ACTIVE MEMBRANES WORKING IN POLYNOMIAL SPACE ⋮ P systems with proteins: a new frontier when membrane division disappears ⋮ Characterizing PSPACE with shallow non-confluent P systems ⋮ Minimal cooperation as a way to achieve the efficiency in cell-like membrane systems ⋮ P systems attacking hard problems beyond NP: a survey ⋮ Nondeterministic Seedless Oritatami Systems and Hardness of Testing Their Equivalence ⋮ P systems with evolutional symport and membrane creation rules solving QSAT ⋮ A polynomial alternative to unbounded environment for tissue P systems with cell division ⋮ Further remarks on \(P\) systems with active membranes, separation, merging, and release rules ⋮ Complexity classes for membrane systems
This page was built for publication: Complexity classes in models of cellular computing with membranes
