Ponencia
One and Two Polarizations, Membrane Creation and Objects Complexity in P Systems
Autor/es | Alhazov, Artiom
Freund, Rudolf Riscos Núñez, Agustín |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2005 |
Fecha de depósito | 2019-04-03 |
Publicado en |
|
ISBN/ISSN | 0-7695-2453-2 |
Resumen | 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 ... 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. |
Identificador del proyecto | TIC2002-04220- C03-01 |
Cita | Alhazov, A., Freund, R. y Riscos Núñez, A. (2005). One and Two Polarizations, Membrane Creation and Objects Complexity in P Systems. En SYNASC'05: 7th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (385-394), Timisoara, Romania: IEEE Computer Society. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
One and Two Polarizations.pdf | 321.3Kb | [PDF] | Ver/ | |