An Investigation into Transition Rule Sets for Optimum-time Firing Squad Synchronization Algorithms on One-dimensional Cellular Automata

概要

論文の詳細を見る
The firing squad synchronization problem has been studied extensively for more than forty years, and a rich variety of synchronization algorithms have been proposed. In the present paper, we describe a computer-assisted investigation into state transition tables for which optimum-time synchronization algorithms have been designed. We show that the first transition rule set designed by Waksman [(1966) Inf. Control, 9: 66-78] includes fundamental errors which cause unsuccessful firings and that ninety-three percent of the rules are redundant. In addition, the transition rule sets reported by Balzer [(1967) Inf. Control, 10: 22-42], Gerken [(1987), Diplomarbeit, Institut für Theoretische Informatik, Technische Universität Braunschweig, 502] and Mazoyer [(1987) Theor. Comput. Sci., 50: 183-238] are found to include several redundant rules. We also present herein a survey and a comparison of the quantitative aspects of the optimum-time synchronization algorithms developed thus far for one-dimensional cellular arrays.
東北大学の論文