期刊
THEORETICAL COMPUTER SCIENCE
卷 371, 期 1-2, 页码 83-105出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2006.10.016
关键词
brane calculi; membrane computing; universality; matrix grammars
Operations with membranes are essential both in brane calculi as well as in membrane computing. In this paper, we attempt to express six basic operations of brane calculi, viz., pino, exo, phago, bud, mate, drip in terms of the membrane computing formalism. We also investigate the computing power of P systems controlled by phago/exo, pino/exo, bud/mate as well as the mate/drip operations. We give an improvement to a characterization of RE using mate/drip operations given in [L. Cardelli, Gh. Paun, An universality result based on mate/drip operations, International Journal of Foundations of Computer Science (in press)]. We also give a characterization of RE using a new operation, called selective mate. We conjecture that it is not possible to obtain Turing completeness using only one of the six operations. We also conjecture that the pairs of operations we have considered for completeness, in this paper, are complete: it is impossible to obtain Turing completeness with any other pair of operations. (c) 2006 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据