Ponencia
On The Semantics of Annihilation Rules in Membrane Computing
Autor/es | Díaz Pernil, Daniel
Freund, Rudolf Gutiérrez Naranjo, Miguel Ángel Leporati, Alberto |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2015 |
Fecha de depósito | 2016-01-21 |
Publicado en |
|
ISBN/ISSN | 978-84-944366-2-8 |
Resumen | It is well known that polarizationless recognizer P systems with active membranes,
without dissolution, with division of elementary and non-elementary membranes,
with antimatter and matter/antimatter annihilation rules ... It is well known that polarizationless recognizer P systems with active membranes, without dissolution, with division of elementary and non-elementary membranes, with antimatter and matter/antimatter annihilation rules can solve all problems in NP when the annihilation rules have (weak) priority over all the other rules. Until now, it was an open problem whether these systems can still solve all NP problems if the priority of the matter/antimatter annihilation rules is removed. In this paper we provide a negative answer to this question: we prove that the class of problems solvable by this model of P systems without priority of the matter/antimatter annihilation rules is exactly P. To the best of our knowledge, this is the rst paper in the literature of P systems where the semantics of applying the rules constitutes a frontier of tractability. |
Agencias financiadoras | Ministerio de Economía y Competitividad (MINECO). España |
Identificador del proyecto | info:eu-repo/grantAgreement/MINECO/TIN2012-37434 |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
131_bwmc2015antiP.pdf | 304.5Kb | [PDF] | Ver/ | |