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

RAIRO - Theoretical Informatics and Applications (2008)

- Volume: 42, Issue: 1, page 55-68
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topYunès, Jean-Baptiste. "An intrinsically non minimal-time Minsky-like 6-states solution to the Firing Squad synchronization problem." RAIRO - Theoretical Informatics and Applications 42.1 (2008): 55-68. <http://eudml.org/doc/250372>.

@article{Yunès2008,

abstract = {
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.
},

author = {Yunès, Jean-Baptiste},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Firing squad; synchronization; firing squad synchronization},

language = {eng},

month = {1},

number = {1},

pages = {55-68},

publisher = {EDP Sciences},

title = {An intrinsically non minimal-time Minsky-like 6-states solution to the Firing Squad synchronization problem},

url = {http://eudml.org/doc/250372},

volume = {42},

year = {2008},

}

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

DA - 2008/1//

PB - EDP Sciences

VL - 42

IS - 1

SP - 55

EP - 68

AB -
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.

LA - eng

KW - Firing squad; synchronization; firing squad synchronization

UR - http://eudml.org/doc/250372

ER -

## References

top- R. Balzer, An 8-state minimal time solution to the firing squad synchronization problem. Inform. Control10 (1967) 22–42.
- J. Duprat, Proof of correctness of the Mazoyer's solution of the firing squad problem in Coq. (2002). URIhttp://hdl.handle.net/2332/792
- E. Goto, A Minimum Time Solution of the Firing Squad Problem. Course Notes for Applied Mathematics298, Harvard University (1962).
- 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.
- T. Jiang, The synchronization of non-uniform networks of finite automata. Inform. Control97 (1992) 234–261.
- K. Kobayashi, The firing squad synchronization problem for a class of polyautomata networks. J. Comput. Syst. Sci.17 (1978) 300–318.
- M. Kutrib and R. Vollmar, The firing squad synchronization problem in defective cellular automata. IEICE T. Inf. Syst.E78-D (1995) 895–900.
- J. Mazoyer, A six-state minimal time solution to the firing squad synchronization problem. Theor. Comput. Sci.50 (1987) 183–238.
- 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).
- M. Minsky, Computation: Finite and Infinite Machines. Prentice-Hall (1967).
- 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.
- K. Noguchi, Simple 8-state minimal time solution to the firing squad synchronization problem. Theor. Comput. Sci.314 (2004) 303–334.
- L. Pierre, Private communication.
- Z. Róka, The firing squad synchronization problem on Cayley graphs. Theor. Comput. Sci.244 (2000) 243–256.
- F. Romani, Cellular Automata Synchronization. Inform. Sciences10 (1976) 299–318.
- 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).
- A. Settle and J. Simon, Smaller solutions for the firing squad. Theor. Comput. Sci.276 (2002) 83–109.
- I. Shinahr, Two and three dimensional firing squad synchronization problem. Inform. Control24 (1974) 163–180.
- 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.
- H. Umeo, An Efficient Design of Two-Dimensional Firing Squad Synchronization Problem. Eighth International Workshop on Cellular Automata, Prague, Czechia (2002).
- H. Umeo, A simple design of time-efficient firing squad synchronization algorithms with fault-tolerance. IEICE T. Inf. Syst.E87-D(3) (2004).
- 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.
- A. Waksman, An optimum solution to the firing squad synchronization. Probl. Inf. Control9 (1966) 66–78.
- J.-B. Yunès, Seven states solutions to the firing squad synchronization. Probl. Theor. Comput. Sci.127 (1994) 313–332.
- J.-B. Yunès, Fault tolerant solutions to the firing squad synchronization problem in linear cellular automata. J. Cell. Automata1 (2006) 253–268.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.