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.
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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ita:2007051/
[1] An 8-state minimal time solution to the firing squad synchronization problem. Inform. Control 10 (1967) 22-42.
,[2] Proof of correctness of the Mazoyer's solution of the firing squad problem in Coq. http://hdl.handle.net/2332/792 (2002).
,[3] A Minimum Time Solution of the Firing Squad Problem. Course Notes for Applied Mathematics 298, Harvard University (1962).
,[4] Synchronization of a bounded degree graph of cellular automata with non uniform delays in time . Theor. Comput. Sci. 356 (2006) 170-185. | MR | Zbl
,[5] The synchronization of non-uniform networks of finite automata. Inform. Control 97 (1992) 234-261. | MR | Zbl
,[6] The firing squad synchronization problem for a class of polyautomata networks. J. Comput. Syst. Sci. 17 (1978) 300-318. | MR | Zbl
,[7] The firing squad synchronization problem in defective cellular automata. IEICE T. Inf. Syst. E78-D (1995) 895-900.
and ,[8] A six-state minimal time solution to the firing squad synchronization problem. Theor. Comput. Sci. 50 (1987) 183-238. | MR | Zbl
,[9] 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] Computation: Finite and Infinite Machines. Prentice-Hall (1967). | MR | Zbl
,[11] The Firing Squad Synchronization Problem, in Sequential Machines. Selected Papers, edited by E.F. Moore Addison-Wesley, Reading MA (1964) 213-214. | Zbl
,[12] Simple 8-state minimal time solution to the firing squad synchronization problem. Theor. Comput. Sci. 314 (2004) 303-334. | MR | Zbl
,[13] Private communication.
,[14] The firing squad synchronization problem on Cayley graphs. Theor. Comput. Sci. 244 (2000) 243-256. | MR | Zbl
,[15] Cellular Automata Synchronization. Inform. Sciences 10 (1976) 299-318. | Zbl
,[16] 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
, and ,[17] Smaller solutions for the firing squad. Theor. Comput. Sci. 276 (2002) 83-109. | MR | Zbl
and ,[18] Two and three dimensional firing squad synchronization problem. Inform. Control 24 (1974) 163-180. | MR | Zbl
,[19] Time-optimal solution of the firing squad synchronization problem for -dimensional rectangles with the general at an arbitrary position. Theor. Comput. Sci. 19 (1982) 305-320. | MR | Zbl
,[20] An Efficient Design of Two-Dimensional Firing Squad Synchronization Problem. Eighth International Workshop on Cellular Automata, Prague, Czechia (2002).
,[21] A simple design of time-efficient firing squad synchronization algorithms with fault-tolerance. IEICE T. Inf. Syst. E87-D(3) (2004).
,[22] 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
, and ,[23] An optimum solution to the firing squad synchronization. Probl. Inf. Control 9 (1966) 66-78. | MR | Zbl
,[24] Seven states solutions to the firing squad synchronization. Probl. Theor. Comput. Sci. 127 (1994) 313-332. | MR | Zbl
,[25] 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 :