An Efficient Mapping Scheme for Embedding Any One-Dimensional Firing Squad Synchronization Algorithm onto Two-Dimensional Arrays - Cellular Automata - page 80

have developed a 9-state optimum-time synchronization algorithm on square ar-
rays and a 6-state linear-time algorithm on rectangular arrays, representing the
smallest such algorithms presented to date.
References
1. R. Balzer: An 8-state minimal time solution to the firing squad synchronization
problem. Information and Control , vol. 10(1967), pp. 22-42.
2. W. T. Beyer: Recognition of topological invariants by iterative arrays. Ph.D. The-
sis, MIT, (1969), pp. 144.
3. E. Goto: A minimal time solution of the firing squad problem. Dittoed course
notes for Applied Mathematics 298, Harvard University, (1962), pp. 52-59, with an
illustration in color.
4. A. Grasselli: Synchronization of cellular arrays: The firing squad problem in two
dimensions. Information and Control , vol. 28(1975), pp. 113-124.
5. J. J. Grefenstette: Network structure and the firing squad synchronization problem.
J. of Computer and System Sciences , vol.26(1983), pp.139-152.
6. K. Kobayashi: The firing squad synchronization problem for two-dimensional ar-
rays. Information and Control , vol. 34(1977), pp. 177-197.
7. M. Kutrib and R. Vollmar: The firing squad synchronization problem in defective
cellular automata. Trans. of IEICE on Inf. and Syst. , vol. E78-D, No. 7(1995), pp.
895-900.
8. M. Maeda and H. Umeo: A design of two-dimensional firing squad synchroniza-
tion algorithms and their implementations. Proc. of 15th Annual Conference of
Japanese Society for Artificial Intelligence , 2C3-05(2001), pp. 1-4.
9. J. Mazoyer: An overview of the firing squad synchronization problem. Lecture Notes
on Computer Science , Springer-Verlag, vol. 316(1986), pp. 82-93.
10. J. Mazoyer: A six-state minimal time solution to the firing squad synchronization
problem. Theoretical Computer Science , vol. 50(1987), pp. 183-238.
11. J. Mazoyer: On optimal solutions to the firing squad synchronization problem.
Theoretical Computer Science , vol. 168(1996), pp. 367-404.
12. M. Minsky: Computation: Finite and infinite machines . Prentice Hall, (1967), pp.
28-29.
13. E. F. Moore: The firing squad synchronization problem. in Sequential Machines,
Selected Papers (E. F. Moore ed.), Addison-Wesley, Reading MA., (1964), pp. 213-
214.
14. F. R. Moore and G. G. Langdon: A generalized firing squad problem. Information
and Control , vol. 12(1968), pp. 212-220.
15. H. B. Nguyen and V. C. Hamacher: Pattern synchronization in two-dimensional
cellular space. Information and Control , vol. 26(1974), pp, 12-23.
16. I. Shinahr: Two- and three-dimensional firing squad synchronization problems.
Information and Control , vol. 24(1974), pp. 163-180.
17. H. Szwerinski: Time-optimum solution of the firing-squad-synchronization-problem
for n-dimensional rectangles with the general at an arbitrary position. Theoretical
Computer Science , vol. 19(1982), pp. 305-320.
18. H. Umeo: A fault-tolerant scheme for optimum-time firing squad synchronization.
Parallel Computing: Trends and Applications , Elsevier Science B.V. 1994, pp. 223-
230.