2012 | OriginalPaper | Chapter
An Adaptive Algorithm for P System Synchronization
Authors : Michael J. Dinneen, Yun-Bum Kim, Radu Nicolescu
Published in: Membrane Computing
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We present an improved solution for the Firing Squad Synchronization Problem (FSSP) for digraph-structured 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 final 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
+ 2
r
+ 3 steps (for all trees structures and many digraphs) and up to 3
e
+ 7 steps, in the worst case for any digraph. Empirical results show our new algorithm for tree-structured P systems yields at least 20% reduction in the number of steps needed to synchronize over the previous best-known algorithm.