Subroutines in P systems and closure properties of their complexity classes

DOI10.1016/J.TCS.2018.06.012zbMATH Open1436.68116OpenAlexW2779653581WikidataQ62678516 ScholiaQ62678516MaRDI QIDQ2285669FDOQ2285669

Authors: Alberto Leporati, Luca Manzoni, Antonio E. Porreca, Claudio Zandron, 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

Recommendations

• P systems simulating oracle computations
• Complexity classes in models of cellular computing with membranes
• Complexity classes for membrane systems
• P Systems with Active Membranes Working in Sublinear Space
• Recent complexity-theoretic results on P systems with active membranes

zbMATH Keywords

membrane computingoracle machinesclosure under exponentiation

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The polynomial-time hierarchy
• The complexity of combinatorial problems with succinct input representation
• An optimal frontier of the efficiency of tissue P systems with cell separation
• The computational power of cell division in P systems: Beating down parallel computers?
• P systems with active membranes: Attacking NP-complete problems
• Title not available (Why is that?)
• Membrane computing and complexity theory: A characterization of PSPACE
• Title not available (Why is that?)
• Uniform Solution of QSAT Using Polarizationless Active Membranes
• A uniform solution to SAT using membrane creation
• Complexity classes in models of cellular computing with membranes
• The computational power of membrane systems under tight uniformity conditions
• P systems simulating oracle computations
• Sublinear-space P systems with active membranes
• Space complexity equivalence of P systems with active membranes and Turing machines
• Membrane division, oracles, and the counting hierarchy
• Simulating elementary active membranes
• Characterising the complexity of tissue P systems with fission rules
• An efficient simulation of polynomial-space Turing machines by P systems with active membranes
• The counting power of P systems with antimatter
• Reaching efficiency through collaboration in membrane systems: dissolution, polarization and cooperation
• Monodirectional P systems
• Computational efficiency of minimal cooperation and distribution in polarizationless P systems with active membranes
• 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
• Constant-space P systems with active membranes
• A gap in the space hierarchy of P systems with active membranes
• Title not available (Why is that?)

Cited In (6)

• Simulating counting oracles with cooperation
• Characterizing PSPACE with shallow non-confluent P systems
• Title not available (Why is that?)
• Some remarks on subclass containment problems for several classes of dpda's
• From \texttt{SAT} to \texttt{SAT}-\texttt{UNSAT} using P systems with dissolution rules
• Turing-Complete Subclasses of CHR

This page was built for publication: Subroutines in P systems and closure properties of their complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2285669)