An intrinsically non minimal-time Minsky-like 6-states solution to the firing squad synchronization problem
Yunès, Jean-Baptiste
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 55-68 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

Here is presented a 6-states non minimal-time solution which is intrinsically Minsky-like and solves the three following problems: unrestricted version on a line, with one initiator at each end of a line and the problem on a ring. We also give a complete proof of correctness of our solution, which was never done in a publication for Minsky's solutions.

Publié le : 2008-01-01
DOI : https://doi.org/10.1051/ita:2007051
Classification:  65Y05,  68Q25,  68Q80,  68W10 
@article{ITA_2008__42_1_55_0,
     author = {Yun\`es, Jean-Baptiste},
     title = {An intrinsically non minimal-time Minsky-like 6-states solution to the firing squad synchronization problem},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {42},
     year = {2008},
     pages = {55-68},
     doi = {10.1051/ita:2007051},
     mrnumber = {2382544},
     zbl = {1148.68410},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2008__42_1_55_0}
}

Yunès, Jean-Baptiste. An intrinsically non minimal-time Minsky-like 6-states solution to the firing squad synchronization problem. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) pp. 55-68. doi : 10.1051/ita:2007051. http://gdmltest.u-ga.fr/item/ITA_2008__42_1_55_0/

[1] R. Balzer, An 8-state minimal time solution to the firing squad synchronization problem. Inform. Control 10 (1967) 22-42.

[2] J. Duprat, Proof of correctness of the Mazoyer's solution of the firing squad problem in Coq. http://hdl.handle.net/2332/792 (2002).

[3] E. Goto, A Minimum Time Solution of the Firing Squad Problem. Course Notes for Applied Mathematics 298, Harvard University (1962).

[4] S. Grigorieff, Synchronization of a bounded degree graph of cellular automata with non uniform delays in time δ⌊log m (δ)⌋. Theor. Comput. Sci. 356 (2006) 170-185. | MR 2217835 | Zbl 1161.68603 | Zbl pre05024254

[5] T. Jiang, The synchronization of non-uniform networks of finite automata. Inform. Control 97 (1992) 234-261. | MR 1157287 | Zbl 0768.68003

[6] K. Kobayashi, The firing squad synchronization problem for a class of polyautomata networks. J. Comput. Syst. Sci. 17 (1978) 300-318. | MR 516841 | Zbl 0392.68043

[7] M. Kutrib and R. Vollmar, The firing squad synchronization problem in defective cellular automata. IEICE T. Inf. Syst. E78-D (1995) 895-900.

[8] J. Mazoyer, A six-state minimal time solution to the firing squad synchronization problem. Theor. Comput. Sci. 50 (1987) 183-238. | MR 907281 | Zbl 0635.68042

[9] J. Mazoyer, A Minimal Time Solution to the Firing Squad Synchronization Problem with Only One Bit of Information Exchanged. Rapport Technique LIP 89.03, École Normale Supérieure de Lyon (1989).

[10] M. Minsky, Computation: Finite and Infinite Machines. Prentice-Hall (1967). | MR 356580 | Zbl 0195.02402

[11] E.F. Moore, The Firing Squad Synchronization Problem, in Sequential Machines. Selected Papers, edited by E.F. Moore Addison-Wesley, Reading MA (1964) 213-214. | Zbl 0192.07602

[12] K. Noguchi, Simple 8-state minimal time solution to the firing squad synchronization problem. Theor. Comput. Sci. 314 (2004) 303-334. | MR 2047900 | Zbl 1072.68071

[13] L. Pierre, Private communication.

[14] Z. Róka, The firing squad synchronization problem on Cayley graphs. Theor. Comput. Sci. 244 (2000) 243-256. | MR 1774396 | Zbl 0945.68135

[15] F. Romani, Cellular Automata Synchronization. Inform. Sciences 10 (1976) 299-318. | Zbl 0334.94017

[16] P. Rosensthiel, J. Fiksel and A. Holliger, Intelligent Graphs: Networks of Finite Automata Capable of Solving Graph Problems, in Graph Theory and Computing, edited by R.C. Read, Academic Press (1972). | MR 354198 | Zbl 0265.94030

[17] A. Settle and J. Simon, Smaller solutions for the firing squad. Theor. Comput. Sci. 276 (2002) 83-109. | MR 1896348 | Zbl 1002.68096

[18] I. Shinahr, Two and three dimensional firing squad synchronization problem. Inform. Control 24 (1974) 163-180. | MR 371539 | Zbl 0292.94039

[19] H. Szwerinski, Time-optimal solution of the firing squad synchronization problem for n-dimensional rectangles with the general at an arbitrary position. Theor. Comput. Sci. 19 (1982) 305-320. | MR 671873 | Zbl 0496.68037

[20] H. Umeo, An Efficient Design of Two-Dimensional Firing Squad Synchronization Problem. Eighth International Workshop on Cellular Automata, Prague, Czechia (2002).

[21] H. Umeo, A simple design of time-efficient firing squad synchronization algorithms with fault-tolerance. IEICE T. Inf. Syst. E87-D(3) (2004).

[22] H. Umeo, M. Maeda and K. Hongyo, A design of symmetrical six-state 3n-step firing squad synchronization algorithms and their implementations. Proceedings of ACRI. Lect. Notes Comput. Sci. 4173 (2006) 157-168. | Zbl 1155.68468

[23] A. Waksman, An optimum solution to the firing squad synchronization. Probl. Inf. Control 9 (1966) 66-78. | MR 191766 | Zbl 1111.68527

[24] J.-B. Yunès, Seven states solutions to the firing squad synchronization. Probl. Theor. Comput. Sci. 127 (1994) 313-332. | MR 1275821 | Zbl 0938.68736

[25] J.-B. Yunès, Fault tolerant solutions to the firing squad synchronization problem in linear cellular automata. J. Cell. Automata 1 (2006) 253-268. | MR 2354081 | Zbl 1135.68495