Complete Problems for a Variant of P Systems with Active Membranes
Author | Porreca, Antonio E.
Leporati, Alberto Mauri, Giancarlo Zandron, Claudio |
Date | 2010 |
Published in | Proceedings of the Eighth Brainstorming Week on Membrane Computing, 243-253. Sevilla, E.T.S. de Ingeniería Informática, 1-5 de Febrero, 2010 |
ISBN/ISSN | 9788461423576 |
Document type | Presentation |
Abstract | 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 ... 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. |
Files | Size | Format | View | Description |
---|---|---|---|---|
19Porreca.pdf | 171.8Kb | ![]() | View/ | |