New Solutions to the Firing Squad Synchronization Problems for Neural and Hyperdag P Systems

Michael J. Dinneen
(University of Auckland)
Yun-Bum Kim
(University of Auckland)
Radu Nicolescu
(University of Auckland)

We propose two uniform solutions to an open question: the Firing Squad Synchronization Problem (FSSP), for hyperdag and symmetric neural P systems, with anonymous cells. Our solutions take e_c+5 and 6e_c+7 steps, respectively, where e_c is the eccentricity of the commander cell of the dag or digraph underlying these P systems. The first and fast solution is based on a novel proposal, which dynamically extends P systems with mobile channels. The second solution is substantially longer, but is solely based on classical rules and static channels. In contrast to the previous solutions, which work for tree-based P systems, our solutions synchronize to any subset of the underlying digraph; and do not require membrane polarizations or conditional rules, but require states, as typically used in hyperdag and neural P systems.

In Gabriel Ciobanu: Proceedings Third Workshop on Membrane Computing and Biologically Inspired Process Calculi 2009 (MeCBIC 2009), Bologna, Italy, 5th September 2009, Electronic Proceedings in Theoretical Computer Science 11, pp. 107–122.
Published: 30th November 2009.

ArXived at: bibtex PDF

Comments and questions to:
For website issues: