4.2 Article

Computing with membranes

期刊

JOURNAL OF COMPUTER AND SYSTEM SCIENCES
卷 61, 期 1, 页码 108-143

出版社

ACADEMIC PRESS INC
DOI: 10.1006/jcss.1999.1693

关键词

membrane structure; P system; recursively enumerable set; matrix grammar; splicing; natural computing

向作者/读者索取更多资源

We introduce a new computability model, of a distributed pal allel type, based on the notion of a membrane structure. Such a structure consists of several cell-like membranes, recurrently placed inside a unique skin membrane. A plane representation is a Venn diagram without intersected sets and with a unique superset. In the regions delimited by the membranes there are placed objects. These objects are assumed to evolve: each object can be transformed in other objects, can pass through a membrane, or can dissolve the membrane in which it is placed. A priority relation between evolution rules can be considered. The evolution is done in parallel for all objects able to evolve. In this way, we obtain a computing device (we call it a P system): start with a certain number of objects in a certain membrane and let the system evolve; if it will halt (no object can further evolve), then the computation is finished, with the result given as the number of objects in a specified membrane. If the development of the system goes forever, then the computation fails to have an output. We prove that the P systems with the possibility of objects to cooperate characterize the recursively enumerable sets of natural numbers; moreover, systems with only two membranes suffice. In fact, we do not need cooperating rules, but we only use catalysts, specified objects which are present in the rules but are not modified by the rule application, One catalyst suffices. A variant is also considered, with the objects being strings over a given alphabet. The evolution rules are now based on string transformations. We investigate the case when either the rewriting operation from Chomsky grammars (with respect to context-free productions) or the splicing operation from H systems investigated in the DNA computing is used, In both cases, characterizations of recursively enumerable languages are obtained by very simple P systems: with three membranes in the rewriting case and four in the splicing case. Several open problems and directions for further research an formulated. (C) 2000 Academic Press.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.2
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据