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

Issue title: Machines, Computations and Universality, Part I

Subtitle: A Geometrical Approach

Article type: Research Article

Authors: Umeo, Hiroshi | Yanagihara, Takashi

Affiliations: Faculty of Information Science and Technology, University of Osaka Electro-Communication, Neyagawa-shi, Hatsu-cho, 18-8, Osaka, 572-8530, Japan. {umeo, yanagihara}@cyt.osakac.ac.jp

Note: [] Address for correspondence: Faculty of Information Science and Technology, University of Osaka Electro-Communication, Neyagawa-shi, Hatsu-cho, 18-8, Osaka, 572-8530, Japan

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

Keywords: Cellular automaton, Firing squad synchronization problem

DOI: 10.3233/FI-2009-0038

Journal: Fundamenta Informaticae, vol. 91, no. 1, pp. 161-178, 2009