We identify a family of decision problems that are hard for some complexity classes de¯ned 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.
Porreca, A., Leporati, A., Mauri, G., Zandron, C. (2010). Complete problems for a variant of P systems with active membranes. ROMANIAN JOURNAL OF INFORMATION SCIENCE AND TECHNOLOGY, 13(2), 197-207.
Complete problems for a variant of P systems with active membranes
PORRECA, ANTONIO ENRICO;LEPORATI, ALBERTO OTTAVIO;MAURI, GIANCARLO;ZANDRON, CLAUDIO
2010
Abstract
We identify a family of decision problems that are hard for some complexity classes de¯ned 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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
