Remarks on the Computational Power of Some Restricted Variants of P Systems with Active Membranes

详细信息    查看全文

• 关键词：Membrane computing ; P systems with active membranes ; Computational complexity
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10105
• 期：1
• 页码：209-232
• 丛书名：Membrane Computing
• ISBN：978-3-319-54072-6
• 卷排序：10105

文摘

In this paper we consider three restricted variants of P systems with active membranes: (1) P systems using send-out communication rules only, (2) P systems using elementary membrane division and dissolution rules only, and (3) polarizationless P systems using dissolution and unit evolution rules only. We show that every problem in \(\mathbf {P}\) can be solved with uniform families of any of these variants using reasonably weak uniformity conditions. This, using known results on the upper bound of the computational power of variants (1) and (3) yields new characterizations of the class \(\mathbf {P}\). In the case of variant (2) we provide a further characterization of \(\mathbf {P}\) by giving a semantic restriction on the computations of P systems of this variant.