We solve affirmatively a new special case of the P conjecture by Gh. Păun, which states that P systems with active membranes without charges and without non-elementary membrane division cannot solve -complete problems in polynomial time. The variant we consider is monodirectional, i.e., without send-in communication rules, shallow, i.e., with membrane structures consisting of only one level besides the external membrane, and deterministic, rather than more generally confluent. We describe a polynomial-time Turing machine simulation of this variant of P systems, exploiting a generalised version of dependency graphs for P systems which, unlike the original version introduced by Cordón-Franco et al., also takes membrane dissolution into account.
Solving a special case of the P conjecture using dependency graphs with dissolution
Manzoni Luca;
2018-01-01
Abstract
We solve affirmatively a new special case of the P conjecture by Gh. Păun, which states that P systems with active membranes without charges and without non-elementary membrane division cannot solve -complete problems in polynomial time. The variant we consider is monodirectional, i.e., without send-in communication rules, shallow, i.e., with membrane structures consisting of only one level besides the external membrane, and deterministic, rather than more generally confluent. We describe a polynomial-time Turing machine simulation of this variant of P systems, exploiting a generalised version of dependency graphs for P systems which, unlike the original version introduced by Cordón-Franco et al., also takes membrane dissolution into account.File | Dimensione | Formato | |
---|---|---|---|
Copertina,indice,contributo.pdf
Accesso chiuso
Tipologia:
Documento in Versione Editoriale
Licenza:
Copyright Editore
Dimensione
357.71 kB
Formato
Adobe PDF
|
357.71 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.