JUCS - Journal of Universal Computer Science 10(5): 502-508, doi: 10.3217/jucs-010-05-0502
On Determinism of Evolution-Communication P Systems
expand article infoArtiom Alhazov
‡ Rovira i Virgili University, Tarragona, Spain and Institute of Mathematics and Computer Science, Academy of Sciences of Moldova, Chisinau, Moldova
Open Access
It is commonly believed that a significant part of the computational power of membrane systems comes from their inherent non-determinism. Recently, R. Freund and Gh. Paun 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 (accepting) 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 generative case, two membranes are enough for universality. For the deterministic systems, we obtain the universality with three membranes, leaving the original problem open.
Membrane computing, P system, Determinism, Computational completeness