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) no. 1, pp. 55-68.

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.

DOI : 10.1051/ita:2007051
Classification : 65Y05, 68Q25, 68Q80, 68W10
Mots-clés : firing squad, synchronization 
@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},
     pages = {55--68},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {1},
     year = {2008},
     doi = {10.1051/ita:2007051},
     mrnumber = {2382544},
     zbl = {1148.68410},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita:2007051/}
}
TY  - JOUR
AU  - Yunès, Jean-Baptiste
TI  - An intrinsically non minimal-time Minsky-like 6-states solution to the firing squad synchronization problem
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
SP  - 55
EP  - 68
VL  - 42
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita:2007051/
DO  - 10.1051/ita:2007051
LA  - en
ID  - ITA_2008__42_1_55_0
ER  - 
%0 Journal Article
%A Yunès, Jean-Baptiste
%T An intrinsically non minimal-time Minsky-like 6-states solution to the firing squad synchronization problem
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2008
%P 55-68
%V 42
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita:2007051/
%R 10.1051/ita:2007051
%G en
%F 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) no. 1, pp. 55-68. doi : 10.1051/ita:2007051. http://archive.numdam.org/articles/10.1051/ita:2007051/

[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 | Zbl

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

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

[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 | Zbl

[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 | Zbl

[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

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

[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 | Zbl

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

[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 | Zbl

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

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

[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 | Zbl

[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

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

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

[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 | Zbl

Cité par Sources :