Repositorio de producción científica de la Universidad de Sevilla

On The Semantics of Annihilation Rules in Membrane Computing

 

Advanced Search
 
Opened Access On The Semantics of Annihilation Rules in Membrane Computing
Cites
Show item statistics
Icon
Export to
Author: Díaz Pernil, Daniel
Freund, Rudolf
Gutiérrez Naranjo, Miguel Ángel
Leporati, Alberto
Department: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
Date: 2015
Published in: Proceedings of the Thirteenth Brainstorming Week on Membrane Computing, 131-142. Sevilla, E.T.S. de Ingeniería Informática, 2-6 de Febrero, 2015,
ISBN/ISSN: 978-84-944366-2-8
Document type: Presentation
Abstract: 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.
Size: 304.5Kb
Format: PDF

URI: http://hdl.handle.net/11441/33036

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)