On generalized communicating P systems with minimal interaction rules
On generalized communicating P systems with minimal interaction rules
复制标题
DOI：
10.1016/j.tcs.2010.08.020
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
E. Csuhaj-Varjú;Sergey Verlan
中科院分区：
文献类型：
--
作者：
E. Csuhaj-Varjú;Sergey Verlan
广义的通信 P 系统是纯粹通信的组织样膜系统，其通信规则仅允许成对的物体移动。在本文中，我们研究了这些系统在八种受限通信规则变体的情况下的威力。我们表明，其中七个限制导致了计算完整性，而使用其余一个，系统只能计算非负整数的有限单例。所获得的结果完成了对广义通信 P 系统计算能力的研究，并为具有简单功能规则的简单架构（与图灵机一样强大）提供了进一步的示例。
Generalized communicating P systems are purely communicating tissue-like membrane systems with communication rules which allow the movement of only pairs of objects. In this paper, we study the power of these systems in the case of eight restricted variants of communication rules. We show that seven of these restrictions lead to computational completeness, while using the remaining one the systems are able to compute only finite singletons of non-negative integers. The obtained results complete the investigations of the computational power of generalized communicating P systems and provide further examples for simple architectures with simple functioning rules which are as powerful as Turing machines.