We compare various computational complexity classes defined within the framework of membrane systems, a distributed parallel computing device which is inspired from the functioning of the cell, with usual computational complexity classes for Turing machines. In particular, we focus our attention on the comparison among complexity classes for membrane systems with active membranes (where new membranes can be created by division of existing membranes) and the classes PSPACE, EXP, and EXPSPACE

Porreca, A., Mauri, G., Zandron, C. (2006). Complexity classes for membrane systems. RAIRO. INFORMATIQUE THEORIQUE ET APPLICATIONS, 40(2), 141-162 [10.1051/ita:2006001].

Complexity classes for membrane systems

PORRECA, ANTONIO ENRICO;MAURI, GIANCARLO;ZANDRON, CLAUDIO
2006

Abstract

We compare various computational complexity classes defined within the framework of membrane systems, a distributed parallel computing device which is inspired from the functioning of the cell, with usual computational complexity classes for Turing machines. In particular, we focus our attention on the comparison among complexity classes for membrane systems with active membranes (where new membranes can be created by division of existing membranes) and the classes PSPACE, EXP, and EXPSPACE
Articolo in rivista - Articolo scientifico
membrane systems; computational complexity; molecular computing
English
2006
40
2
141
162
none
Porreca, A., Mauri, G., Zandron, C. (2006). Complexity classes for membrane systems. RAIRO. INFORMATIQUE THEORIQUE ET APPLICATIONS, 40(2), 141-162 [10.1051/ita:2006001].
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/2489
Citazioni
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 24
Social impact