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