Abstract
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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bernardini, F., Gheorghe, M., Margenstern, M., Verlan, S.: How to synchronize the activity of all components of a P system? In: Vaszil, G. (ed.) Proc. Intern. Workshop Automata for Cellular and Molecular Computing, MTA SZTAKI, Budapest, Hungary, pp. 11–22 (2007)
Goto, E.: A minimum time solution of the firing squad problem. Harward Univ. Course Notes for Applied Mathematics, 298 (1962)
Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. American Mathematical Society 7, 48–50 (1956)
Mazoyer, J.: A six-state minimal time solution to the firing squad synchronization problem. Theoretical Science 50, 183–238 (1987)
Minsky, M.: Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs (1967)
Păun, G.: Membrane Computing. An Introduction. Springer, Heidelberg (2002)
Prim, R.C.: Shortest connection networks and some generalizations. Bell System Technical Journal 36, 1389–1401 (1957)
Spellman, P.T., Sherlock, G.: Reply whole-cell synchronization - effective tools for cell cycle studies. Trends in Biotechnology 22, 270–273 (2004)
Umeo, H., Maeda, M., Fujiwara, N.: An efficient mapping scheme for embedding any one-dimensional firing squad synchronization algorithm onto two-dimensional arrays. In: Bandini, S., Chopard, B., Tomassini, M. (eds.) ACRI 2002. LNCS, vol. 2493, pp. 69–81. Springer, Heidelberg (2002)
Schmid, H., Worsch, T.: The firing squad synchronization problem with many generals for one-dimensional CA. In: Proc. IFIP TCS 2004, pp. 111–124 (2004)
Yunès, J.-B.: Seven-state solution to the firing squad synchronization problem. Theoretical Computer Sci. 127, 313–332 (1994)
The P systems web page, http://ppage.psystems.eu
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alhazov, A., Margenstern, M., Verlan, S. (2009). Fast Synchronization in P Systems. In: Corne, D.W., Frisco, P., Păun, G., Rozenberg, G., Salomaa, A. (eds) Membrane Computing. WMC 2008. Lecture Notes in Computer Science, vol 5391. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-95885-7_9
Download citation
DOI: https://doi.org/10.1007/978-3-540-95885-7_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-95884-0
Online ISBN: 978-3-540-95885-7
eBook Packages: Computer ScienceComputer Science (R0)