Published April 5, 2016
| Version v1
Publication
Using Central Nodes to Improve P System Synchronization
Description
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.
Additional details
Identifiers
- URL
- https://idus.us.es/handle/11441/39473
- URN
- urn:oai:idus.us.es:11441/39473