Portal de Periódicos da CAPES

HOW TO SYNCHRONIZE THE ACTIVITY OF ALL COMPONENTS OF A P SYSTEM?

2008; World Scientific; Volume: 19; Issue: 05 Linguagem: Inglês

10.1142/s0129054108006224

1793-6373

Francesco Bernardini, Marian Gheorghe, Maurice Margenstern, Sergey Verlan,

semigroups and automata theory

We consider the problem of synchronizing the activity of all the membranes of a P system. After pointing at 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. One algorithm is non-deterministic and it works in the time 3h, where h is the height of the tree defining the membrane structure of the considered P system. The other algorithm is deterministic and it works in time 4n + 2h, where n is the number of membranes of the considered P system. Finally, we suggest various directions to continue this work.