On the Power of Deterministic EC P Systems

Abstract

It is commonly believed that a signi¯cant part of the computational power of membrane systems comes from their inherent non-determinism. Re- cently, R. Freund and Gh. P¸aun have considered deterministic P systems, and formulated the general question whether the computing (generative) capacity of non-deterministic P systems is strictly larger than the (recognizing) capacity of their deterministic counterpart. In this paper, we study the computational power of deterministic P systems in the evolution{communication framework. It is known that, in the genera- tive case, two membranes are enough for universality. For the deterministic systems, we obtain the universality with three membranes, leaving the original problem open.