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

On Communication Complexity in Evolution-Communication P Systems

Opened Access On Communication Complexity in Evolution-Communication P Systems
Exportar a
Autor: Adorna, Henry N.
Paun, Gheorghe
Pérez Jiménez, Mario de Jesús
Departamento: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Fecha: 2010
Publicado en: Proceedings of the Eighth Brainstorming Week on Membrane Computing, 1-21. Sevilla, E.T.S. de Ingeniería Informática, 1-5 de Febrero, 2010
ISBN/ISSN: 978-84-614-2357-6
Tipo de documento: Ponencia
Resumen: Looking for a theory of communication complexity for P systems, we consider here so-called evolution-communication (EC for short) P systems, where objects evolve by multiset rewriting rules without target commands and pass through membranes by means of symport/antiport rules. (Actually, in most cases below we use only symport rules.) We first propose a way to measure the communication costs by means of “quanta of energy” (produced by evolution rules and) consumed by communication rules. EC P systems with such costs are proved to be Turing complete in all three cases with respect to the relation between evolution and communication operations: priority of communication, mixing the rules without priority for any type, priority of evolution (with the cost of communication increasing in this ordering in the universality proofs). More appropriate measures of communication complexity are then defined, as dynamical parameters, counting the communication steps or the number (and the...
[Ver más]
Tamaño: 230.2Kb
Formato: PDF


Mostrar el registro completo del ítem

Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones