Within the framework of membrane systems, distributed parallel computing models inspired by the functioning of the living cell, various computational complexity classes have been defined, which can be compared against the computational complexity classes defined for Turing machines. Here some issues and results concerning computational complexity of membrane systems are discussed. 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 membranes which exist in the system in a given moment) and the classes PSPACE, EXP, and EXPSPACE. © 2010 Springer-Verlag Berlin Heidelberg.
Mauri, G., Leporati, A., Porreca, A., Zandron, C. (2010). Computational Complexity Aspects in Membrane Computing. In Programs, proofs, processes. Proc. CiE 2010 (pp.317-320). Berlin : Springer [10.1007/978-3-642-13962-8_35].
Computational Complexity Aspects in Membrane Computing
MAURI, GIANCARLO;LEPORATI, ALBERTO OTTAVIO;PORRECA, ANTONIO ENRICO;ZANDRON, CLAUDIO
2010
Abstract
Within the framework of membrane systems, distributed parallel computing models inspired by the functioning of the living cell, various computational complexity classes have been defined, which can be compared against the computational complexity classes defined for Turing machines. Here some issues and results concerning computational complexity of membrane systems are discussed. 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 membranes which exist in the system in a given moment) and the classes PSPACE, EXP, and EXPSPACE. © 2010 Springer-Verlag Berlin Heidelberg.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
