Published December 18, 2017
| Version v1
Publication
Subroutines in P Systems and Closure Properties of Their Complexity Classes
Description
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 PC C, where PC 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 P. 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, abstracting
from the technical details which depend on the speci c variant of P system, in order to
describe a general strategy for proving closure under exponentiation.
Additional details
Identifiers
- URL
- https://idus.us.es/handle/11441/67736
- URN
- urn:oai:idus.us.es:11441/67736