Presentation
On the Power of Deterministic EC P Systems
Author/s | Alhazov, Artiom |
Date | 2004 |
Published in |
|
ISBN/ISSN | 84-688-6101-4 |
Abstract | It is commonly believed that a signi¯cant part of the computational
power of membrane systems comes from their inherent non-determinism. Re-
cently, R. Freund and Gh. P¸aun have considered deterministic P systems, ... It is commonly believed that a signi¯cant part of the computational power of membrane systems comes from their inherent non-determinism. Re- cently, R. Freund and Gh. P¸aun 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 (recognizing) 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 genera- tive case, two membranes are enough for universality. For the deterministic systems, we obtain the universality with three membranes, leaving the original problem open. |
Files | Size | Format | View | Description |
---|---|---|---|---|
ARTIOMEC.pdf | 98.08Kb | ![]() | View/ | |