Artículo
Cell-like P systems with polarizations and minimal rules
Autor/es | Pan, Linqiang
Orellana Martín, David Song, Bosheng Pérez Jiménez, Mario de Jesús |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2020 |
Fecha de depósito | 2021-04-28 |
Publicado en |
|
Resumen | P systems with active membranes are a class of computation models in the area ofmembrane computing, which are inspired from the mechanism by which chemicalsinteract and cross cell membranes. In this work, we consider a ... P systems with active membranes are a class of computation models in the area ofmembrane computing, which are inspired from the mechanism by which chemicalsinteract and cross cell membranes. In this work, we consider a normal form of P systemswith active membranes, called cell-like P systems with polarizations and minimal rules,where rules are minimal in the sense that an object evolves to exactly one object withthe application of an evolution rule or a communication rule, or an object evolves to twoobjects that are assigned to the two new generated membranes by applying a division rule.The present work investigates the computational power of P systems with polarizationsand minimal rules. Specifically, results about Turing universality and non-universality areobtained with the combination of the number of membranes, the number of polarizations,and the types of rules. We also show that polarizationless P systems with minimal rules areequivalent to Turing machines working in a polynomial space, that is, the class of problemsthat can be solved in polynomial time by polarizationless P systems with minimal rules isequal to the classPSPACE. |
Agencias financiadoras | Ministerio de Economia, Industria y Competitividad (MINECO). España |
Identificador del proyecto | TIN2017-89842-P (MABICAP) |
Cita | Pan, L., Orellana Martín, D., Song, B. y Pérez Jiménez, M.d.J. (2020). Cell-like P systems with polarizations and minimal rules. Theoretical Computer Science, 816 (May 2020) |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Cell-like P systems with polar ... | 804.7Kb | [PDF] | Ver/ | |