Subroutines in P systems and closure properties of their complexity classes

DOI10.1016/J.TCS.2018.06.012MaRDI QIDQ2285669zbMATH OpenOpenAlexWikidataFDO

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

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)

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

Cites work

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

Cited in

(6)

• From \texttt{SAT} to \texttt{SAT}-\texttt{UNSAT} using P systems with dissolution rules
• Turing-Complete Subclasses of CHR
• Simulating counting oracles with cooperation
• Characterizing PSPACE with shallow non-confluent P systems
• scientific article; zbMATH DE number 680708 (Why is no real title available?)
• Some remarks on subclass containment problems for several classes of dpda's

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)