A New Time-Optimum Synchronization Algorithm for Rectangle Arrays

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

Abstrakty

EN

The firing squad synchronization problem on cellular automata has been studied extensively for more than forty years, and a rich variety of synchronization algorithms have been proposed so far. In the present paper, we propose a new optimum-time algorithm for synchronizing two-dimensional cellular automata. The algorithm can synchronize any two-dimensional rectangle array of size m ×n in optimum m + n + max(m, n)- 3 steps. A partial implementation of the algorithm for small cellular arrays is also given.

Słowa kluczowe

EN

cellular automata; firing squad synchronization problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 87, nr 2
• Strony: 155--164
• Opis fizyczny: bibliogr. 16 poz., wykr.

Twórcy

autor

Umeo H.

autor

Uchino H.

• Faculty of Information Science and Technology, Osaka Electro-Communication University, 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] W. T. Beyer: Recognition of topological invariants by iterative arrays. Ph.D. Thesis, MIT, (1969), pp. 144.
• [3] Hans-D., Gerken. (1987): Uber Synchronisations - Probleme bei Zellularautomaten. Diplomarbeit, Institut fiir Theoretische Informatik, Technische Universitat Braunschweig, pp. 50.
• [4] E. Goto: A minimal time solution of the firing squad problem. Dittoed course notes for Applied Mathematics 298, Harvard University, (1962), pp. 52-59.
• [5] J. Mazoyer: A six-state minimal time solution to the firing squad synchronization problem. Theoretical Computer Science, vol. 50 (1987), pp. 183-238.
• [6] 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.
• [7] H. Schmid: Synchronisationsprobleme fur zellulare Automaten mit mehreren Generalen. Diplomarbeit, Universitat Karsruhe, (2003).
• [8] I. Shinahr: Two- and three-dimensional firing squad synchronization problems. Information and Control, vol. 24(1974), pp. 163-180.
• [9] 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.
• [10] H. Umeo: A simple design of time-efficient firing squad synchronization algorithms with fault-tolerance. IEICE Trans, on Information and Systems, Vol. E87-D, No.3, 2004, pp.733-739.
• [11] H. Umeo, M. Hisaoka, and S. Akiguchi: Twelve-state optimum-time synchronization algorithm for two-dimensional rectangular cellular arrays. Proc. of 4th International Conference on Unconventional Computing: UC 2005, LNCS 3699, (2005), pp.214-223.
• [12] H. Umeo, M. Hisaoka and T. Sogabe: A survey on optimum-time firing squad synchronization algorithms for one-dimensional cellular automata. Intern. J. of Unconventional Computing, 2005, vol. 1, pp.403-426.
• [13] H. Umeo, M. Hisaoka, M. Teraoka and M. Maeda: Several new generalized linear- and optimum-time synchronization algorithms for two-dimensional rectangular arrays. Proc. of 4th International Conference on Machines, Computations and Universality: MCU 2004, LNCS 3354 (M. Margenstern(Ed.), (2005), pp.223-232.
• [14] H. Umeo, M. Maeda, M. Hisaoka and M. Teraoka: A state-efficient mapping scheme for designing two-dimensional firing squad synchronization algorithms. Fundamenta Informaticae, Vol.74(2006), pp.603-623.
• [15] H. Umeo and H. Uchino: A new time-optimum synchronization algorithm for two-dimensional cellular arrays. Proc. of Intern. Conf. on Computer Aided Systems Theory, EUROCAST 2007 ,(RM. Diaz, F. Pichler, A.Q. Arencibia (Eds.)), LNCS 4739, pp. 604-611, (2007).
• [16] A. Waksman: An optimum solution to the firing squad synchronization problem. Information and Control, vol. 9 (1966), pp. 66-78.