We prove that recognizer P systems with active membranes using polynomial space characterize the complexity class PSPACE. This result holds for both confluent and nonconfluent systems, and independently of the use of membrane division rules.
Porreca, A., Leporati, A., Mauri, G., Zandron, C. (2011). P systems with active membranes working in polynomial space. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 22(1), 65-73 [10.1142/S0129054111007836].
P systems with active membranes working in polynomial space
PORRECA, ANTONIO ENRICO;LEPORATI, ALBERTO OTTAVIO;MAURI, GIANCARLO;ZANDRON, CLAUDIO
2011
Abstract
We prove that recognizer P systems with active membranes using polynomial space characterize the complexity class PSPACE. This result holds for both confluent and nonconfluent systems, and independently of the use of membrane division rules.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
