Published March 30, 2016 | Version v1
Publication

Complete Problems for a Variant of P Systems with Active Membranes

Description

We identify a family of decision problems that are hard for some complexity classes defined in terms of P systems with active membranes working in polynomial time. Furthermore, we prove the completeness of these problems in the case where the systems are equipped with a form of priority that linearly orders their rules. Finally, we highlight some possible connections with open problems related to the computational complexity of P systems with active membranes.

Additional details

Identifiers

URL
https://idus.us.es/handle/11441/39113
URN
urn:oai:idus.us.es:11441/39113