loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Seventh International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC'05)
One and Two Polarizations, Membrane Creation and Objects Complexity in P Systems
Timisoara, Romania
September 25-September 29
ISBN: 0-7695-2453-2
Artiom Alhazov, Rovira i Virgili University and Academy of Sciences of Moldova
Rudolf Freund, Vienna University of Technology
Agustín Riscos-Núñez, University of Sevilla

We improve, by using register machines, some existing universality results for specific models of P systems. P systems with membrane creation are known to generate all recursively enumerable sets of vectors of non-negative integers, even when no region (except the environment) contains more than one object of the same kind. We here show that they generate all recursively enumerable languages, and two membrane labels are sufficient (the same result holds for accepting all recursively enumerable vectors of non-negative integers). Moreover, at most two objects are present inside the system at any time in the generative case. Then we prove that 10 + m symbols are enough to generate any recursively enumerable language over m symbols.

P systems with active membranes without polarizations are known to generate all recursively enumerable sets of vectors of non-negative integers. We show that they generate all recursively enumerable languages; four starting membranes with three labels or seven starting membranes with two labels are sufficient. P systems with active membranes and two polarizations are known to generate/accept all recursively enumerable sets of vectors of non-negative integers, only using rules of rewriting and sending objects out. We show that accepting can be done by deterministic systems. Finally, remarks and open questions are presented.

Citation:
Artiom Alhazov, Rudolf Freund, Agustín Riscos-Núñez, "One and Two Polarizations, Membrane Creation and Objects Complexity in P Systems," synasc, pp.385-394, Seventh International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.