Complexity classes for membrane systems

被引：25

作者：

Porreca, Antonio E. ^{[1
]}

Mauri, Giancarlo ^{[1
]}

Zandron, Claudio ^{[1
]}

机构：

[1] Univ Milano Bicocca, DISCo, I-20122 Milan, Italy

来源：

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS | 2006年 / 40卷 / 02期

关键词：

membrane systems; computational complexity; molecular computing;

D O I：

10.1051/ita:2006001

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：141 / 162

页数：22

共 15 条

[1] Alhazov A, 2003, FUND INFORM, V58, P67
[2] [Anonymous], 1997, HDB FORMAL LANGUAGES, DOI DOI 10.1007/978-3-662-07675-0
[3] Gutiérrez-Naranjo MA, 2005, LECT NOTES COMPUT SC, V3699, P105
[4] GUTIERREZNARANJ.M, 2005, P 1 INT WORKSH THEOR, P61
[5] KRISHNA SN, 1999, ROMANIAN J INFORM SC, V2
[6] Papadimitriou C.H., 1994, Computational Complexity
[7] Paun G, 2001, DISCRETE MATH & THEO, P94
[8] Computing with membranes
Päun, G
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2000, 61 (01) : 108 - 143
[9] PAUN G, 1999, 102 CDMTCS AUCKL U
[10] Paun G., 1998, 208 TUCS

← 1 2 →