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 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.
Shallow non-confluent P systems / Leporati, Alberto; Manzoni, Luca; Mauri, Giancarlo; Porreca Antonio, E.; Zandron, Claudio. - STAMPA. - 10105:(2017), pp. 307-316. ( 17th International Conference on Membrane Computing, CMC 2016 Milan, Italy 2016) [10.1007/978-3-319-54072-6_19].
Shallow non-confluent P systems
Manzoni Luca;
2017-01-01
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 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.| File | Dimensione | Formato | |
|---|---|---|---|
|
cop.,indice. Manzoni.pdf
Accesso chiuso
Tipologia:
Documento in Versione Editoriale
Licenza:
Copyright Editore
Dimensione
195.42 kB
Formato
Adobe PDF
|
195.42 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
