We prove that non-confluent (i.e., strongly nondeterministic) P systems with active membranes working in polynomial time are able to simulate polynomial-space nondeterministic Turing machines, and thus to solve all f problems. Unlike the confluent case, this result holds for shallow P systems. In particular, depth 1 (i.e., only one membrane nesting level and using elementary membrane division only) already suffices, and neither dissolution nor send-in communication rules are needed.
Leporati, A., Manzoni, L., Mauri, G., Porreca, A., Zandron, C. (2017). Shallow non-confluent P systems. In Membrane Computing, 17th International Conference, CMC 2016, Milan, Italy, July 25-29 2016, Revised Selected Papers (pp.307-316). Springer Verlag [10.1007/978-3-319-54072-6_19].
Shallow non-confluent P systems
LEPORATI, ALBERTO OTTAVIOPrimo
;MANZONI, LUCASecondo
;MAURI, GIANCARLO;PORRECA, ANTONIO ENRICOPenultimo
;ZANDRON, CLAUDIO
2017
Abstract
We prove that non-confluent (i.e., strongly nondeterministic) P systems with active membranes working in polynomial time are able to simulate polynomial-space nondeterministic Turing machines, and thus to solve all f problems. Unlike the confluent case, this result holds for shallow P systems. In particular, depth 1 (i.e., only one membrane nesting level and using elementary membrane division only) already suffices, and neither dissolution nor send-in communication rules are needed.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
