RAIRO - Theoretical Informatics and Applications
- RAIRO - Theoretical Informatics and Applications April 2006, 40 : pp 141-162
- © EDP Sciences, 2006
- DOI: 10.1051/ita:2006001 (About DOI)
- Published online by Cambridge University Press: 30 March 2011
Research Article
Complexity classes for membrane systems
Porreca, Antonio E.a1, Mauri, Giancarloa1 and Zandron, Claudioa1
a1 DISCo, Università di Milano-Bicocca, Italy; {porreca; mauri; zandron}@disco.unimib.it
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.
(Online publication July 20 2006)
Key Words:
- Membrane systems;
- computational complexity;
- molecular computing.
Mathematics Subject Classification:
- 68Q05;
- 68Q15
