Fast Synchronization in P Systems
作者： Artiom Alhazov , Maurice Margenstern , Sergey Verlan
DOI: 10.1007/978-3-540-95885-7_9
关键词:
摘要: We consider the problem of synchronizing activity all membranes a P system. After pointing connection with similar dealt in field cellular automata, where is called firing squad synchronization , FSSP for short, we provide two algorithms to solve this systems. One algorithm non-deterministic and works 2h + 3 steps, other deterministic 3h h height tree describing membrane structure.
springer.com
archives-ouvertes.fr
sci-hub.st 参考文章(11)
Hubert Schmid, Thomas Worsch, The Firing Squad Synchronization Problem with Many Generals for One-Dimensional CA IFIP TCS. pp. 111- 124 ,(2004) , 10.1007/1-4020-8141-3_11
Joseph B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem Proceedings of the American Mathematical Society. ,vol. 7, pp. 48- 50 ,(1956) , 10.1090/S0002-9939-1956-0078686-7
J.B. Yunès, Seven-state solutions to the Firing Squad Synchronization Problem Theoretical Computer Science. ,vol. 127, pp. 313- 332 ,(1994) , 10.1016/0304-3975(94)90045-0
Paul T Spellman, Gavin Sherlock, Reply: whole-culture synchronization – effective tools for cell cycle studies Trends in Biotechnology. ,vol. 22, pp. 270- 273 ,(2004) , 10.1016/J.TIBTECH.2004.04.010
Marvin L. Minsky, Computation: Finite and Infinite Machines ,(1967)
R. C. Prim, Shortest Connection Networks And Some Generalizations Bell System Technical Journal. ,vol. 36, pp. 1389- 1401 ,(1957) , 10.1002/J.1538-7305.1957.TB01515.X
Jacques Mazoyer, A six-state minimal time solution to the firing squad synchronization problem Theoretical Computer Science. ,vol. 50, pp. 183- 238 ,(1987) , 10.1016/0304-3975(87)90124-1
Gheorghe Paun, Membrane Computing: An Introduction ,(2002)
FRANCESCO BERNARDINI, MARIAN GHEORGHE, MAURICE MARGENSTERN, SERGEY VERLAN, HOW TO SYNCHRONIZE THE ACTIVITY OF ALL COMPONENTS OF A P SYSTEM International Journal of Foundations of Computer Science. ,vol. 19, pp. 1183- 1198 ,(2008) , 10.1142/S0129054108006224
1Hiroshi Umeo, Masashi Maeda, Norio Fujiwara, An Efficient Mapping Scheme for Embedding Any One-Dimensional Firing Squad Synchronization Algorithm onto Two-Dimensional Arrays cellular automata for research and industry. pp. 69- 81 ,(2002) , 10.1007/3-540-45830-1_7