An intrinsically non minimal-time Minsky-like 6-states solution to the Firing Squad synchronization problem

 Access to full text

 Full (PDF)

 Access to full text

 Full (PDF)

1. R. Balzer, An 8-state minimal time solution to the firing squad synchronization problem. Inform. Control10 (1967) 22–42.  
2. J. Duprat, Proof of correctness of the Mazoyer's solution of the firing squad problem in Coq. (2002).  URIhttp://hdl.handle.net/2332/792
3. E. Goto, A Minimum Time Solution of the Firing Squad Problem. Course Notes for Applied Mathematics298, Harvard University (1962).  
4. S. Grigorieff, Synchronization of a bounded degree graph of cellular automata with non uniform delays in time $\delta \lfloor {log}_m\left(\delta \right)\rfloor$. Theor. Comput. Sci.356 (2006) 170–185.  
5. T. Jiang, The synchronization of non-uniform networks of finite automata. Inform. Control97 (1992) 234–261.  
6. K. Kobayashi, The firing squad synchronization problem for a class of polyautomata networks. J. Comput. Syst. Sci.17 (1978) 300–318.  
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.  
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).  
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.  
12. K. Noguchi, Simple 8-state minimal time solution to the firing squad synchronization problem. Theor. Comput. Sci.314 (2004) 303–334.  
13. L. Pierre, Private communication.  
14. Z. Róka, The firing squad synchronization problem on Cayley graphs. Theor. Comput. Sci.244 (2000) 243–256.  
15. F. Romani, Cellular Automata Synchronization. Inform. Sciences10 (1976) 299–318.  
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).  
17. A. Settle and J. Simon, Smaller solutions for the firing squad. Theor. Comput. Sci.276 (2002) 83–109.  
18. I. Shinahr, Two and three dimensional firing squad synchronization problem. Inform. Control24 (1974) 163–180.  
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.  
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.  
23. A. Waksman, An optimum solution to the firing squad synchronization. Probl. Inf. Control9 (1966) 66–78.  
24. J.-B. Yunès, Seven states solutions to the firing squad synchronization. Probl. Theor. Comput. Sci.127 (1994) 313–332.  
25. J.-B. Yunès, Fault tolerant solutions to the firing squad synchronization problem in linear cellular automata. J. Cell. Automata1 (2006) 253–268.