On Determinism of Evolution-Communication P Systems
| dc.creator | Alhazov,Artiom | |
| dc.date | 2004 | |
| dc.date.accessioned | 2024-02-06T12:52:57Z | |
| dc.date.available | 2024-02-06T12:52:57Z | |
| dc.description | 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. | |
| dc.format | text/html | |
| dc.identifier | https://doi.org/10.3217/jucs-010-05-0502 | |
| dc.identifier | https://lib.jucs.org/article/28223/ | |
| dc.identifier.uri | https://openrepository.mephi.ru/handle/123456789/8543 | |
| dc.language | en | |
| dc.publisher | Journal of Universal Computer Science | |
| dc.relation | info:eu-repo/semantics/altIdentifier/eissn/0948-6968 | |
| dc.relation | info:eu-repo/semantics/altIdentifier/pissn/0948-695X | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | J.UCS License | |
| dc.source | JUCS - Journal of Universal Computer Science 10(5): 502-508 | |
| dc.subject | Membrane computing | |
| dc.subject | P system | |
| dc.subject | Determinism | |
| dc.subject | Computational completeness | |
| dc.title | On Determinism of Evolution-Communication P Systems | |
| dc.type | Research Article |