How to Synchronize Cellular Automata – Recent Developments –

Issue title: Interdisciplinary Nature of Information Processing Special Issue Dedicated to Giancarlo Mauri on the Occasion of His 70th Birthday

Guest editors: Alberto Dennunzio, Gheorghe Păun, Grzegorz Rozenberg and Claudio Zandron

Article type: Research Article

Authors: Umeo, Hiroshi^{; *}

Affiliations: Institute of Informatics, University of Osaka Electro-Communication, Neyagawa-shi, Hatsu-cho, 18-8, Osaka, 572-8530, Japan. umeo@cyt.osakac.ac.jp

Correspondence: [*] Address for correspondence: University of Osaka Electro-Communication, Neyagawa-shi, Hatsu-cho, 18-8, Osaka, 572-8530, Japan. A part of this work has been supported by JSPS 16K00026

Abstract: 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.

Keywords: Cellular automaton, Firing squad synchronization problem, FSSP

DOI: 10.3233/FI-2020-1889

Journal: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 393-419, 2020