We investigate the influence that the flow of information in membrane systems has on their computational complexity. In particular, we analyse the behaviour of P systems with active membranes where communication only happens from a membrane towards its parent, and never in the opposite direction. We prove that these “monodirectional P systems” are, when working in polynomial time and under standard complexity-theoretic assumptions, much less powerful than unrestricted ones: indeed, they characterise classes of problems defined by polynomial-time Turing machines with NP oracles, rather than the whole class PSPACE of problems solvable in polynomial space.

Leporati, A., Manzoni, L., Mauri, G., Porreca, A., Zandron, C. (2016). Monodirectional P systems. NATURAL COMPUTING, 15(4), 551-564 [10.1007/s11047-016-9565-2].

Monodirectional P systems

LEPORATI, ALBERTO OTTAVIO
;
MANZONI, LUCA
Secondo
;
MAURI, GIANCARLO;PORRECA, ANTONIO ENRICO
Penultimo
;
ZANDRON, CLAUDIO
Ultimo
2016

Abstract

We investigate the influence that the flow of information in membrane systems has on their computational complexity. In particular, we analyse the behaviour of P systems with active membranes where communication only happens from a membrane towards its parent, and never in the opposite direction. We prove that these “monodirectional P systems” are, when working in polynomial time and under standard complexity-theoretic assumptions, much less powerful than unrestricted ones: indeed, they characterise classes of problems defined by polynomial-time Turing machines with NP oracles, rather than the whole class PSPACE of problems solvable in polynomial space.
Articolo in rivista - Articolo scientifico
membrane computing; complexity theory
English
551
564
14
Leporati, A., Manzoni, L., Mauri, G., Porreca, A., Zandron, C. (2016). Monodirectional P systems. NATURAL COMPUTING, 15(4), 551-564 [10.1007/s11047-016-9565-2].
Leporati, A; Manzoni, L; Mauri, G; Porreca, A; Zandron, C
File in questo prodotto:
File Dimensione Formato  
Paper.pdf

accesso aperto

Descrizione: Preprint
Dimensione 231.79 kB
Formato Adobe PDF
231.79 kB Adobe PDF Visualizza/Apri
Monodirectional P Systems - NaCo (2016).pdf

Solo gestori archivio

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 795.28 kB
Formato Adobe PDF
795.28 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/137686
Citazioni
  • Scopus 20
  • ???jsp.display-item.citation.isi??? 17
Social impact