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

available in:   PDF (148 kB) PS (50 kB)
 
get:  
Similar Docs BibTeX   Write a comment
  
get:  
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