On The Semantics of Annihilation Rules in Membrane Computing
- Others:
- Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
- Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
- Universidad de Sevilla. TIC193: Computación Natural
- Universidad de Sevilla. FQM296: Topología Computacional y Matemática Aplicada
- Ministerio de Economía y Competitividad (MINECO). España
Description
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.
Abstract
Ministerio de Economía y Competitividad TIN2012-37434
Additional details
- URL
- https://idus.us.es/handle/11441/33036
- URN
- urn:oai:idus.us.es:11441/33036
- Origin repository
- USE