P systems with active membranes are a variant of P systems where membranes play an active role during the computation, for example by dividing existing membranes in order to create new ones. In this way, an exponential number of membranes can be obtained in polynomial time, and then used in parallel to attack computationally hard problems. Many interesting questions arise concerning the trade-off between time and space needed to solve various classes of computational problems by means of such membrane systems. In this paper we overview the main results presented in the literature concerning this subject.

A survey on space complexity of P systems with active membranes

Manzoni Luca;
2018-01-01

Abstract

P systems with active membranes are a variant of P systems where membranes play an active role during the computation, for example by dividing existing membranes in order to create new ones. In this way, an exponential number of membranes can be obtained in polynomial time, and then used in parallel to attack computationally hard problems. Many interesting questions arise concerning the trade-off between time and space needed to solve various classes of computational problems by means of such membrane systems. In this paper we overview the main results presented in the literature concerning this subject.
2018
Pubblicato
https://link.springer.com/article/10.1007/s12572-018-0227-8
File in questo prodotto:
File Dimensione Formato  
Leporati2018_Article_ASurveyOnSpaceComplexityOfPSys.pdf

Accesso chiuso

Tipologia: Documento in Versione Editoriale
Licenza: Copyright Editore
Dimensione 465.81 kB
Formato Adobe PDF
465.81 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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11368/2947810
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 10
social impact