Published January 21, 2016
| Version v1
Publication
On The Semantics of Annihilation Rules in Membrane Computing
Contributors
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-37434Additional details
Identifiers
- URL
- https://idus.us.es/handle/11441/33036
- URN
- urn:oai:idus.us.es:11441/33036