Presentation
Using Central Nodes to Improve P System Synchronization
Author/s | Dinneen, Michael J.
Kim, Yun-Bum Nicolescu, Radu |
Publication Date | 2011 |
Deposit Date | 2016-04-05 |
Published in |
|
ISBN/ISSN | 9788461518371 |
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 ... 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. |
Files | Size | Format | View | Description |
---|---|---|---|---|
08DKN_FSSP_LNCS_Revised_Promot ... | 329.3Kb | [PDF] | View/ | |