P systems with active membranes constitute a very interesting model of computation, defined in the framework of Membrane Computing. Since their appeareance, they have been used to solve computationally difficult problems (usually in the classes NP and PSPACE), due to their ability to generate an exponential size workspace in a polynomial number of time steps. Several computational complexity techniques have thus been applied to study their computing power and efficiency. In this extended abstract I will briefly survey some of these techniques and the main results which have been obtained in the last few years by the group of Membrane Computing at the University of Milano-Bicocca (also known as the "Milano Team"), sometimes in collaboration with collegues from the international Membrane Computing community. © 2014 Springer-Verlag Berlin Heidelberg.

Leporati, A. (2014). Computational complexity of P systems with active membranes. In Membrane computing : 14th International Conference, CMC 2013, Chişinău, Republic of Moldova, August 20-23, 2013, revised selected papers (pp.19-32). Springer Verlag [10.1007/978-3-642-54239-8_3].

Computational complexity of P systems with active membranes

LEPORATI, ALBERTO OTTAVIO
2014

Abstract

P systems with active membranes constitute a very interesting model of computation, defined in the framework of Membrane Computing. Since their appeareance, they have been used to solve computationally difficult problems (usually in the classes NP and PSPACE), due to their ability to generate an exponential size workspace in a polynomial number of time steps. Several computational complexity techniques have thus been applied to study their computing power and efficiency. In this extended abstract I will briefly survey some of these techniques and the main results which have been obtained in the last few years by the group of Membrane Computing at the University of Milano-Bicocca (also known as the "Milano Team"), sometimes in collaboration with collegues from the international Membrane Computing community. © 2014 Springer-Verlag Berlin Heidelberg.
paper
Theoretical Computer Science; Computer Science (all)
English
14th International Conference on Membrane Computing, CMC 2013
2013
Alhazov, A; Cojocaru, S; Gheorghe, M; Rogozhin, Y; Rozenberg, G; Salomaa, A
Membrane computing : 14th International Conference, CMC 2013, Chişinău, Republic of Moldova, August 20-23, 2013, revised selected papers
9783642542381
2014
8340
19
32
http://springerlink.com/content/0302-9743/copyright/2005/
none
Leporati, A. (2014). Computational complexity of P systems with active membranes. In Membrane computing : 14th International Conference, CMC 2013, Chişinău, Republic of Moldova, August 20-23, 2013, revised selected papers (pp.19-32). Springer Verlag [10.1007/978-3-642-54239-8_3].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/155491
Citazioni
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
Social impact