| 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, ...
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.
|
On the Power of Deterministic EC P Systems
[PDF]
