Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 10 / Issue 5

available in:   PDF (148 kB) PS (50 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-010-05-0502


On Determinism of Evolution-Communication P Systems

Artiom Alhazov (Rovira i Virgili University, Tarragona, Spain and Institute of Mathematics and Computer Science, Academy of Sciences of Moldova, Moldova)

Abstract: 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.

Keywords: Computational completeness, Determinism, Membrane computing, P system

Categories: F.4.2, F.4.3