Subroutines in P systems and closure properties of their complexity classes
From MaRDI portal
Publication:2285669
DOI10.1016/j.tcs.2018.06.012zbMath1436.68116OpenAlexW2779653581WikidataQ62678516 ScholiaQ62678516MaRDI QIDQ2285669
Antonio E. Porreca, Luca Manzoni, Claudio Zandron, Alberto Leporati, Giancarlo Mauri
Publication date: 8 January 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/11368/2947808
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)
Related Items (3)
From \texttt{SAT} to \texttt{SAT}-\texttt{UNSAT} using P systems with dissolution rules ⋮ Simulating counting oracles with cooperation ⋮ Characterizing PSPACE with shallow non-confluent P systems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The computational power of membrane systems under tight uniformity conditions
- Membrane computing and complexity theory: A characterization of PSPACE
- A uniform solution to SAT using membrane creation
- The complexity of combinatorial problems with succinct input representation
- The polynomial-time hierarchy
- Complexity classes in models of cellular computing with membranes
- The computational power of cell division in P systems: Beating down parallel computers?
- The counting power of P systems with antimatter
- Reaching efficiency through collaboration in membrane systems: dissolution, polarization and cooperation
- Monodirectional P systems
- Characterising the complexity of tissue P systems with fission rules
- Space complexity equivalence of P systems with active membranes and Turing machines
- An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Separation
- Membrane Division, Oracles, and the Counting Hierarchy
- P Systems Simulating Oracle Computations
- Remarks on the Computational Power of Some Restricted Variants of P Systems with Active Membranes
- Shallow Non-confluent P Systems
- Simulating Turing Machines with Polarizationless P Systems with Active Membranes
- Simulating Elementary Active Membranes
- Uniform Solution of QSAT Using Polarizationless Active Membranes
- Computational Efficiency of Minimal Cooperation and Distribution in Polarizationless P Systems with Active Membranes
- Sublinear-Space P Systems with Active Membranes
- Constant-Space P Systems with Active Membranes
- An Efficient Simulation of Polynomial-Space Turing Machines by P Systems with Active Membranes
This page was built for publication: Subroutines in P systems and closure properties of their complexity classes
