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
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 in questo prodotto:
| 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.
