A Small Five-State Non-Optimum-Time Solution to the Firing Squad Synchronization Problem - A Geometrical Approach -

• Autorzy: Umeo H. , Yanagihara T.
• Języki publikacji: EN

Abstrakty

EN

An existence or non-existence of five-state firing squad synchronization protocol has been a long-standing, famous open problem for a long time. In this paper, we answer partially to this problem by proposing a small five-state firing squad synchronization algorithm that can synchronize any one-dimensional cellular array of length n = 2^k in 3n - 3 steps for any positive integer k.

Słowa kluczowe

EN

cellular automation; firing squad synchronization problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 1
• Strony: 161--178
• Opis fizyczny: bibliogr. 21 poz., tab., wykr.

Twórcy

autor

Umeo H.

autor

Yanagihara T.

• Faculty of Information Science and Technology University of Osaka Electro-Communication Neyagawa-shi, Hatsu-cho, 18-8, Osaka, 572-8530, Japan,

Bibliografia

• [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] A. Berthiaume, T. Bittner, L. Perkovic, A. Settle and J. Simin: Bounding the firing squad synchronization problem on a ring. Theoretical Computer Science, 320 (2004), 213-228.
• [3] P. C. Fischer: Generation of primes by a one-dimensional real-time iterative array. J. of ACM, vol.12, No.3 (1965), pp.388-394.
• [4] H.-D. Gerken: über Synchronisations - Probleme bei Zellularautomaten. Diplomarbeit, Institut für Theoretische Informatik, Technische Universität Braunschweig, (1987), pp. 50.
• [5] E. Goto: A minimal time solution of the firing squad problem. Dittoed course notes for Applied Mathematics 298, Harvard University, (1962), pp. 52-59.
• [6] J. Mazoyer: A six-state minimal time solution to the firing squad synchronization problem. Theoretical Computer Science, vol. 50 (1987), pp. 183-238.
• [7] M. L. Minsky: Computation: Finite and infinite machines. Prentice Hall, (1967), pp. 28-29.
• [8] 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.
• [9] P. Sanders: Massively parallel search for transition-tables of polyautomata. In Proc. of the VI International Workshop on Parallel Processing by Cellular Automata and Arrays, (C. Jesshope, V. Jossifov and W. Wilhelmi (editors)), Akademie, (1994), pp.99-108.
• [10] A. Settle and J. Simon: Smaller solutions for the firing squad. Theoretical Computer Science, 276 (2002), 83-109.
• [11] H. Umeo, M. Hisaoka and T. Sogabe: A survey on firing squad synchronization algorithms for onedimensional cellular automata. International Journal of Unconventional Computing, Vol.1(2005), pp.403-426.
• [12] H. Umeo and N. Kamikawa: Four-state solutions to the firing squad synchronization problem based on Wolfram's rule 150, (2007) (a draft).
• [13] H. Umeo, M. Maeda and K. Hongyo: A design of symmetrical six-state 3n-step firing squad synchronization algorithms and their implementations. Proc. of 7th International Conference on Cellular Automata for Research and Industry, ACRI2006, LNCS 4173(2006), pp.157-168.
• [14] H. Umeo and T. Yanagihara: A smallest five-state solution to the firing squad synchronization problem. Proceedings of 5th International Conference on Machines, Computations, and Universality: MCU 2007 (J. Durand-Lose and M. Margenstern (Eds.)), LNCS 4664 (2007), 291-302.
• [15] H. Umeo, J. B. Yunès, and N. Kamikawa: About 4-states solutions to the firing squad synchronization problem. Proc. of 8th International Conference on Cellular Automata for Research and Industry: ACRI 2008, LNCS 5191 (2008), pp.108-113.
• [16] H. Umeo, N. Kamikawa, and J. B. Yunès: A family of smallest symmetrical four-state firing squad synchronization protocols forring arrays, (2008) (Parallel Processing Letters).
• [17] R. Vollmar: On cellular automata with a finite number of state changes. Computing, Supplementum, vol. 3(1981), pp.181-191.
• [18] A. Waksman: An optimum solution to the firing squad synchronization problem. Information and Control, vol. 9 (1966), pp. 66-78.
• [19] J. B. Yunès: Seven-state solution to the firing squad synchronization problem. Theoretical Computer Science, 127(1994), pp.313-332.
• [20] J. B. Yunès: An intrinsically non minimal-timeMinsky-like 6 states solution to the firing squad synchronization problem. Theoretical Informatics and Applications, (2008), Vol.42, No.1, pp.55-68.
• [21] J. B. Yunès: A 4-states algebraic solution to linear cellular automata synchronization, Information Processing Letters, (2008), Vol. 19, Issue 2, pp.71-75.