Ponencia
The Efficiency of Tissue P Systems with Cell Separation Relies on the Environment
Autor/es | Macías Ramos, Luis Felipe
Pérez Jiménez, Mario de Jesús Riscos Núñez, Agustín Rius Font, Miquel Valencia Cabrera, Luis |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2012 |
Fecha de depósito | 2019-04-09 |
Publicado en |
|
ISBN/ISSN | 978-963-311-372-1 |
Resumen | The classical definition of tissue P systems includes a distinguished
alphabet with the special assumption that its elements are
available in an arbitrarily large amount of copies. These objects are
shared in a distinguished ... The classical definition of tissue P systems includes a distinguished alphabet with the special assumption that its elements are available in an arbitrarily large amount of copies. These objects are shared in a distinguished place of the system, called the environment. This ability of having infinitely many copies of some objects has been widely exploited in the design of efficient solutions to computationally hard problems by means of tissue P systems. This paper deals with computational aspects of tissue P systems with cell separation where there is no such environment as described above. The main result is that only tractable problems can be efficiently solved by using this kind of P systems. Bearing in mind that NP-complete problems can be efficiently solved by using tissue P systems without environment and with cell division, we deduce that in the framework of tissue P systems without environment, the kind of rules (separation versus division) provides a new frontier of the tractability of decision problems. |
Identificador del proyecto | TIN2009-13192
P08-TIC-04200 |
Cita | Macías Ramos, L.F., Pérez Jiménez, M.d.J., Riscos Núñez, A., Rius Font, M. y Valencia Cabrera, L. (2012). The Efficiency of Tissue P Systems with Cell Separation Relies on the Environment. En CMC13: 13th International Conference on Membrane Computing (277-290), Budapest, Hungary: Computer and Automation Research Institute Hungarian Academy of Sciences. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
the-efficiency.pdf | 782.0Kb | [PDF] | Ver/ | |