Portal de Periódicos da CAPES

Fast Synchronization in P Systems

2009; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-540-95885-7_9

1611-3349

Artiom Alhazov, Maurice Margenstern, Sergey Verlan,

semigroups and automata theory

We consider the problem of synchronizing the activity of all membranes of a P system. After pointing the connection with a similar problem dealt with in the field of cellular automata, where the problem is called the firing squad synchronization problem, FSSP for short, we provide two algorithms to solve this problem for P systems. One algorithm is non-deterministic and works in 2h + 3 steps, the other is deterministic and works in 3h + 3 steps, where h is the height of the tree describing the membrane structure.