Subroutines in P systems and closure properties of their complexity classes

The literature on membrane computing describes several variants of P systems whose complexity classes C are “closed under exponentiation”, that is, they satisfy the inclusion ▪, where ▪ is the class of problems solved by polynomial-time Turing machines with oracles for problems in C. This closure au...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2020-01, Vol.805, p.193-205
Main Authors: Leporati, Alberto, Manzoni, Luca, Mauri, Giancarlo, Porreca, Antonio E., Zandron, Claudio
Format: Article
Language:English
Subjects:
Closure under exponentiation
Membrane computing
Oracle machines
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The literature on membrane computing describes several variants of P systems whose complexity classes C are “closed under exponentiation”, that is, they satisfy the inclusion ▪, where ▪ is the class of problems solved by polynomial-time Turing machines with oracles for problems in C. This closure automatically implies closure under many other operations, such as regular operations (union, concatenation, Kleene star), intersection, complement, and polynomial-time mappings, which are inherited from ▪. Such results are typically proved by showing how elements of a family ▪ of P systems can be embedded into P systems simulating Turing machines, which exploit the elements of ▪ as subroutines. Here we focus on the latter construction, providing a description that, by abstracting from the technical details which depend on the specific variant of P system, describes a general strategy for proving closure under exponentiation. We also provide an example implementation using polarizationless P systems with active membranes and minimal cooperation.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2018.06.012