P systems with active membranes are a variant of P systems where the membranes can be created during the computation by division of existing ones. Using this feature, one can create an exponential number of membranes in a polynomial time, and use them in parallel to solve computationally hard problems, such as problems in NP or even in PSPACE. This possibility raises many interesting questions concerning the trade–off between time and space needed to solve various classes of computational problems by means of membrane systems. In this paper we concentrate on P systems with active membranes working in sublinear space, with a survey on recent research results concerning such systems

Zandron, C., Leporati, A., Manzoni, L., Mauri, G., Porreca, A. (2014). P systems with active membranes working in sublinear space. In Membrane Computing 15th International Conference, CMC 2014, Prague, Czech Republic, August 20-22, 2014, Revised Selected Papers (pp.35-47). Springer [10.1007/978-3-319-14370-5_3].

P systems with active membranes working in sublinear space

ZANDRON, CLAUDIO;LEPORATI, ALBERTO OTTAVIO;MANZONI, LUCA;MAURI, GIANCARLO;PORRECA, ANTONIO ENRICO
2014

Abstract

P systems with active membranes are a variant of P systems where the membranes can be created during the computation by division of existing ones. Using this feature, one can create an exponential number of membranes in a polynomial time, and use them in parallel to solve computationally hard problems, such as problems in NP or even in PSPACE. This possibility raises many interesting questions concerning the trade–off between time and space needed to solve various classes of computational problems by means of membrane systems. In this paper we concentrate on P systems with active membranes working in sublinear space, with a survey on recent research results concerning such systems
slide + paper
membrane computing; computational complexity
English
International Conference on Membrane Computing (CMC) August 20-22
2014
Gheorghe, M; Rozenberg, G; Salomaa, A; Sosík, P; Zandron, C
Membrane Computing 15th International Conference, CMC 2014, Prague, Czech Republic, August 20-22, 2014, Revised Selected Papers
978-3-319-14369-9
2014
8961
35
47
reserved
Zandron, C., Leporati, A., Manzoni, L., Mauri, G., Porreca, A. (2014). P systems with active membranes working in sublinear space. In Membrane Computing 15th International Conference, CMC 2014, Prague, Czech Republic, August 20-22, 2014, Revised Selected Papers (pp.35-47). Springer [10.1007/978-3-319-14370-5_3].
File in questo prodotto:
File Dimensione Formato  
Paper.pdf

Solo gestori archivio

Dimensione 344 kB
Formato Adobe PDF
344 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/60388
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
Social impact