How to Synchronize Cellular Automata – Recent Developments –.

• Autorzy: Umeo Hiroshi

Identyfikatory

DOI

10.3233/FI-2020-1889

• Języki publikacji: EN

Abstrakty

EN

The synchronization in cellular automata has been known as the firing squad synchronization problem (FSSP) since its development, in which it was originally proposed by Myhill and reported by Moore in 1964 to synchronize all/some parts of self-reproducing cellular automata. The problem has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms has been proposed not only for one-dimensional (1D) arrays but also for multi-dimensional arrays. In the present paper, we construct a survey on the study of FSSP algorithms, focusing on recent developments.

Słowa kluczowe

EN

cellular automaton; firing squad synchronization problem; FSSP

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 171, nr 1-4
• Strony: 393--419
• Opis fizyczny: Bibliogr. 65 poz., rys., tab., wykr.

Twórcy

autor

Umeo Hiroshi

• Institute of Informatics, University of Osaka Electro-Communication, Neyagawa-shi, Hatsu-cho, 18-8, Osaka, 572-8530, Japan

Bibliografia

• [1] Balzer R. An 8-state minimal time solution to the firing squad synchronization problem. Information and Control, 1967. 10(1):22-42. URL https://doi.org/10.1016/S0019-9958(67)90032-0.
• [2] Berthiaume A, Bittner T, Perković L, Settle A, and Simon J. Bounding the firing synchronization problem on a ring. Theoretical Computer Science, 2004. 320(2-3):213-228. URL https://doi.org/10.1016/j.tcs.2004.01.036.
• [3] Beyer WT. Recognition of topological invariants by iterative arrays. Ph.D. Thesis, MIT, 1969 pp.144.
• [4] Culik II K, and Dube S. An efficient solution of the firing mob problem. Theoretical Computer Science, 1991. 91(1):57-69. URL https://doi.org/10.1016/0304-3975(91)90267-6.
• [5] Dinneen MJ, Kim Y-B, and Nicolescu R. Faster synchronization in P systems. Natural Computing, 2012. 11(1):107-115. doi:10.1007/s11047-011-9271-z.
• [6] Fischer PC. Generation of primes by a one-dimensional real-time iterative array. J. of ACM, 1965. 12(3):388-394. doi:10.1145/321281.321290.
• [7] Gerken, H. D.: Über Synchronisationsprobleme bei Zellularautomaten. Diplomarbeit, Institut für Theoretische Informatik, Technische Universität Braunschweig, pp.1-50 (1987).
• [8] Goto E. A minimal time solution of the firing squad problem. Dittoed course notes for Applied Mathematics 298 (with an illustration in color), Harvard University, 1962 pp. 52-59.
• [9] Goto E. Some puzzles on automata. In Toward computer sciences (T. Kitagawa ed.), (in Japanease), Kyouritsu Publishing, 1966 pp. 67-91.
• [10] Gruska J, Torre SL, and Parente M. The firing squad synchronization problem on squares, toruses and rings. Intern. J. of Foundations of Computer Science, 2007. 18(3):637-654. URL https://doi.org/10.1142/S0129054107004875.
• [11] Herman GT. Models for cellular interactions in development without polarity of individual cells. Paer I. General description and the problem of universal computing ability. Int. J. Systems Sci., 1971. 2(3):271-289. URL https://doi.org/10.1080/00207727108920195.
• [12] Herman GT. Models for cellular interactions in development without polarity of individual cells. Part II. Problems of synchronization and regulation. Int. J. Systems Sci., 1972. 3(2):149-175. URL https://doi.org/10.1080/00207727208920256.
• [13] Herman GT, Liu W-H, Rowland S, and Walker A. Synchronization of growing cellular arrays. Information and Control C103-122, (1974). URL https://doi.org/10.1016/S0019-9958(74)90833-X.
• [14] Imai K, and Morita K. Firing squad synchronization problem in reversible cellular automata. Theor. Comput. Sci.. 1966. 165(2):475-482. URL https://doi.org/10.1016/0304-3975(96)00016-3.
• [15] Imai K, Morita K, and Sako K. Firing squad synchronization problem in number-conserving cellular automata. Fundam. Inform. 2002. 52(1-3):133-141.
• [16] Mazoyer J. An overview of the firing squad synchronization problem. Springer-Verlag, LNCS vol 316, 1986 pp. 82-93. doi:10.1007/3-540-19444-4_16.
• [17] Mazoyer J. A six-state minimal time solution to the firing squad synchronization problem. Theoretical Computer Science, 1987. 50(2):183-238. URL https://doi.org/10.1016/0304-3975(87)90124-1.
• [18] Mazoyer J. A minimal-time solution to the FSSP without recursive call to itself and with bounded slope of signals. Unpublished draft, 1997 pp. 1-25.
• [19] Minsky M. Computation: Finite and infinite machines. Prentice-Hall, 1967. ISBN- 0-13-165563-9.
• [20] Mazoyer J. Synchronization of growing lines of automata. Unpublished manuscript, 2013 pp 1-57.
• [21] Moore EF. The firing squad synchronization problem. In Sequential Machines, Selected Papers (E. F. Moore, ed.), Addison-Wesley, Reading MA., 1964 pp. 213-214.
• [22] Moore FR, and Langdon GG. A generalized firing squad problem. Information and Control, 1968. 12(3):212-220. URL https://doi.org/10.1016/S0019-9958(68)90309-4.
• [23] Ng WL. Partial solutions for the firing squad synchronization problem on rings. ProQuest publications, Ann Arbor, MI, 2011. pp.1-363. ISBN-9781249877578.
• [24] Noguchi K. Simple 8-state minimal time solution to the firing squad synchronization problem. Theoretical Computer Science, 2004. 314(3):303-334. URL https://doi.org/10.1016/S0304-3975(03)00425-0.
• [25] Rosenstiehl P, Fiksel JR, Holliger A. Intelligent graphs: networks of finite automata capable of solving graph problems. in Graph Theory and Computing (Read, R.C. ed.), Academic Press, New York, 1972. URL https://hal.archives-ouvertes.fr/hal-00259588.
• [26] Sanders P. 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. KITopen-ID: 329894.
• [27] Schmid H. Synchronisationprobleme für zelluläre Automaten mit mehreren Generälen. Diploma thesis, Universität Karlsruhe, 2003.
• [28] Schmid H, and Worsch T. The firing squad synchronization problem with many generals for one-dimensional CA. Proc. of IFIP World Congress, vol 155. 2004. pp.111-124. doi:10.1007/1-4020-8141-3_11.
• [29] Settle A, and Simon J. Smaller solutions for the firing squad. Theoretical Computer Science, 2002. 276(1-2):83-109. URL https://doi.org/10.1016/S0304-3975(01)00191-8.
• [30] Shinahr I. Two- and three-dimensional firing squad synchronization problems. Information and Control, 1974. 24(2):163-180. URL https://doi.org/10.1016/S0019-9958(74)80055-0.
• [31] Szwerinski H. Time-optimum solution of the firing-squad-synchronization-problem for n-dimensional rectangles with the general at an arbitrary position. Theoretical Computer Science, 1982. 19(3):305-320. URL https://doi.org/10.1016/0304-3975(82)90040-8.
• [32] Umeo H. A simple design of time-efficient firing squad synchronization algorithms with fault-tolerance. IEICE Trans. on Information and Systems, Vol. 2004. E87-D(3):733-739. ISSN-0916-8532.
• [33] Umeo H. Problem solving on one-bit-communication cellular automata. Chapter 6, In Simulating Complex Systems by Cellular Automata, (ed. A. G. Hoekstra, J. Kroc, and P.M.A. Sloot), Springer, Berlin-Heidelberg, 2010 pp.117-144. doi:10.1007/978-3-642-12203-3_6.
• [34] Umeo H. Synchronizing square arrays in optimum-time. International Journal of General Systems, 2012. 41(6):617-631. URL https://doi.org/10.1080/03081079.2012.695901.
• [35] Umeo H. Time-optimum smaller-state synchronizers for cellular automata. In: Computing with New Resources, Gruska Festschrift, (C. S. Calude, R. Freivalds, and K. Iwama (Eds.), Springer Switzerland, LNCS 8808, 2014 pp.129-145. doi:10.1007/978-3-319-13350-8_10.
• [36] Umeo H. A class of non-optimum-time FSSP algorithms. In Advances in Unconventional Computing (A. Adamatzky ed.), Springer Switzerland, 2017 pp. 495-521. doi:10.1007/978-3-319-33924-5_20.
• [37] Umeo H. Cellular automata, Firing squad synchronization problem in. In Encyclopedia of Complexity and System Science, R. A. Meyers (Ed.), Springer, New York 2018. URL https://doi.org/10.1007/978-0-387-30440-3_211.
• [38] Umeo H, Hirota M, Imai K, and Sogabe T. A new reconstruction and the first implementation of Goto’s FSSP algorithm. Applied mathematics and Computations, 2018. 318:92-108. URL https://doi.org/10.1016/j.amc.2017.05.015.
• [39] Umeo H, Hisaoka M, and Akiguchi S. A twelve-state optimum-time synchronization algorithm for two-dimensional rectangular arrays. Proc. of the 4th International Conference on Unconventional Computation : UC 2005, LNCS 3699, 2005 pp. 214-223. doi:10.1007/11560319_20.
• [40] Umeo H, Hisaoka M, Michisaka K, Nishioka K, and Maeda M. Some new generalized synchronization algorithms and their implementations for large scale cellular automata. Proc. of the 3rd International Conference on Unconventional Models of Computation: UMC 2002, LNCS 2509. 2002 pp. 276-286. doi:10.1007/3-540-45833-6_23.
• [41] Umeo H, and Imai K. A class of minimum-time minimum-state-change generalized FSSP algorithms. Proc. of ACRI 2016, S. El Yacoubi et al. (Eds.), LNCS 9863, Springer International Publishing Switzerland, 2016 pp. 1-11. doi:10.1007/978-3-319-44365-2_14.
• [42] Umeo H, Imai K, and Sousa A. A generalized minimum-time minimum-state-change FSSP algorithm. Proc. of the 4th International Conference on the Theory and Practise of Natural Computing, TPNC 2015, LNCS 9477, Springer International Publishing Switzerland, 2015 pp. 161-173. doi:10.1007/978-3-319-26841-5_13.
• [43] Umeo H, Imai K, and Sousa A. A design of generalized minimum-state-change FSSP algorithms. Natural Computing. 2018. 17(3):441-453. doi:10.1007/s11047-017-9265-2,
• [44] Umeo H, Kamikawa N, and Fujita G. The smallest FSSP partial solutions for one-dimensional ring cellular automata. Proc. of ICTAC 2018 LNCS 11187, 2018 pp. 455-471. doi:10.1007/978-3-030-02508-3_24.
• [45] Umeo H, Kamikawa N, Nishioka K, and Akiguchi S. Generalized firing squad synchronization protocols for one-dimensional cellular automata - a survey. Acta Physica Polonica B, Proceedings Supplement. 2010. 3(2):267-289. URL http://th-www.if.uj.edu.pl/acta/sup3/t1.htm.
• [46] Umeo, H., Kamikawa, N., Maeda, M., and Fujita, G.: Implementations of FSSP algorithms on faulttolerant cellular arrays. Proceedings of ACRI 2018, LNCS 11115. 2018 pp. 274- 285. doi:10.1007/978-3-319-99813-8-25.
• [47] Umeo H, Kamikawa N, and Yunès J-B. A family of smallest symmetrical four-state firing squad synchronization protocols for ring arrays. Parallel Processing Letters, 2009. Vol.19(2):299-313. URL https://doi.org/10.1142/S0129626409000237.
• [48] Umeo H, and Kubo K. A seven-state time-optimum square synchronizer. Proc. of the 9th International Conference on Cellular Automata for Research and Industry, LNCS 6350, Springer-Verlag, 2010 pp. 219-230. doi:10.1007/978-3-642-15979-4_24.
• [49] Umeo H, Maeda M, and Fujiwara N. An efficient mapping scheme for embedding any one-dimensional firing squad synchronization algorithm onto two-dimensional arrays. Proc. of the 5th International Conference on Cellular Automata for Research and Industry, LNCS 2493, Springer-Verlag, 2002 pp. 69-81. doi:10.1007/3-540-45830-1_7.
• [50] Umeo H, Maeda M, Hisaoka M, and Teraoka M. A state-efficient mapping scheme for designing two-dimensional firing squad synchronization algorithms. Fundamenta Informaticae, 2006. 74(4):603-623. URL http://content.iospress.com/journals/fundamenta-informaticae/145/2
• [51] Umeo H, Maeda M, and Hongyo K. 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. doi:10.1007/11861201_21.
• [52] Umeo H, Kubo K, and Nishide K. A class of time-optimum FSSP algorithms for multi-dimensional cellular arrays. Communications in Nonlinear Science and Numerical Simulation, 2015. 21(1-3):200-209. URL https://doi.org/10.1016/j.cnsns.2014.07.031.
• [53] Umeo H, and Nomura A. A state-efficient zebra-like implementation of synchronization algorithms for 2D rectangular cellular arrays. BIOMATH 2012. 1(1):1-6. ISSN-1314-684X, 1314-7218.
• [54] Umeo H, Nishide K, and Yamawaki T. A new optimum-time firing squad synchronization algorithm for two-dimensional rectangle arrays - one-sided recursive halving based. Proc. of the Intern. Conf. on Models of Computation in Context, Computability in Europe 2011, CiE 2011, LNCS 6735, (B. Löwe et al. (Eds.)), 2011 pp. 290-299. doi:10.1007/978-3-642-21875-0_31.
• [55] Umeo H, Yamawaki T, and Nishide K. An optimu-time firing squad synchronization algorithm for two-dimensional rectangle arrays - Freezing-thawing technique based -, International Journal of Cellular Automata (ISSN: 1557-5997 (online)), 2012. 7:31-46.
• [56] Umeo H, and Yanagihara T. Smallest implementations of optimum-time firing squad synchronization algorithms for one-bit-communication cellular automata. Proc. of the 2011 International Conference on Parallel Computing and Technology, PaCT 2011, LNCS 6873. 2011 pp. 210-223. ISBN-978-3-642-23177-3.
• [57] Umeo H, and Yanagihara T. A smallest five-state solution to the firing squad synchronization problem. Proc. of 5th Intern. Conf. on Machines, Computations, and Universality, MCU 2007, LNCS 4664, 2007 pp. 292-302. doi:10.1007/978-3-540-74593-8_25.
• [58] Varshavsky VI, Marakhovsky VB, and Peschansky VA. Synchronization of Interacting Automata. Mathematical Systems Theory, 1970. 4(2):212-230. doi:10.1007/BF01691105.
• [59] Vollmar R. Some remarks about the efficiency of polyautomata. Inter. J. of Theoretical Physics, 1982. 21(12):1007-1015. doi:10.1007/BF02084165.
• [60] Yunès J-B. Seven-state solution to the firing squad synchronization problem. Theoretical Computer Science, 1994. 127(2):313-332. URL https://doi.org/10.1016/0304-3975(94)90045-0.
• [61] Yunès J-B. Fault Tolerant Solutions to the Firing Squad Synchronization Problem in Linear Cellular Automata. J. Cellular Automata (ISSN: 1557-5997 (online)), 2006. 1(3):253-268.
• [62] Yunès J-B. A 4-states algebraic solution to linear cellular automata synchronization. Information Processing Letters, 2008. 107(2):71-75. URL https://doi.org/10.1016/j.ipl.2008.01.009.
• [63] Yunès J-B. An intrinsically non minimal-time Minsky-like 6 states solution to the firing squad synchronization problem. Theoretical Informatics and Applications, 2008. 42(1):55-68. doi:10.1051/ita:2007051.
• [64] Yunès J-B. Goto’s construction and Pascal’s triangle: new insights into cellular automata synchronization. Proc. of JAC 2008, HAL archives, hal-00274000, 2008 pp. 195-203.
• [65] Waksman A. An optimum solution to the firing squad synchronization problem. Information and Control, 1966. 9(1):66-78. URL https://doi.org/10.1016/S0019-9958(66)90110-0.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).