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

Using Central Nodes to Improve P System Synchronization

 

Advanced Search
 
Opened Access Using Central Nodes to Improve P System Synchronization
Cites
Show item statistics
Icon
Export to
Author: Dinneen, Michael J.
Kim, Yun-Bum
Nicolescu, Radu
Date: 2011
Published in: Proceedings of the Ninth Brainstorming Week on Membrane Computing, 125-150. Sevilla, E.T.S. de Ingeniería Informática, 31 de enero-4 de febrero, 2011
ISBN/ISSN: 9788461518371
Document type: Presentation
Abstract: We present an improved solution for the Firing Squad Synchronization Problem (FSSP) for digraph-based P systems. We improve our previous FSSP algorithm by allowing the general to delegate a more central cell in the P system to send the nal command to synchronize. With e being the eccentricity of the general and r denoting the radius of the underlying digraph, our new algorithm guarantees to synchronize all cells of the system, between e + 2r + 3 steps (for all trees structures and many digraphs) and up to 3e + 7 steps, in the worst case for any digraph. Empirical results show our new algorithm for tree-based P systems yields at least 20% reduction in the number of steps needed to synchronize over the previous best-known algorithm.
Size: 329.3Kb
Format: PDF

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

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

This item appears in the following Collection(s)