B105 2次元セルラオートマトン上での同期アルゴリズム(ロジック,アルゴリズム)

概要

論文の詳細を見る
The famous firing squad synchronization problem is stated as follows : Given a one-dimensional array of n identical cellular automata, including a "general" at the left end which is activated at time t=0, we want to design the automata so that, at some future time, all the cells will simultaneously and, for the first time, enter a special "firing" state. The problem was originally proposed by J. Myhill in 1957, presented in Moore [5], to synchronize all parts of a self-reproducing machine. A lot of literatures have been published on this topic [1-17]. In this paper we propose a simple and efficient embedding of one-dimensional firing squad synchronization algorithms onto multi-dimensional arrays and give some implementations on two-dimensional arrays. Several 2-D synchronization algorithms have been presented in Shinar [6], Grasselli [7], and Szwerinski [9], however, practical implementations are rarely found. We give the following implementations together with firing configurations on computer simulation. Most of them have relatively small number of internal states. [Theorem 1] There exists a 9-state 2-D CA which can synchronize n x n square arrays in optimum 2n-2 steps. [Theorem 2] There exists a 6-state 2-D CA which can synchronize m x n rectangular arrays in 2(m+n)-4 steps. [Theorem 3] There exists a 6-state 2-D CA that can synchronize m x n cellular arrays with some isolated rectangular holes in 2(m+n)-4 steps. [Theorem 4] There exists a 21-state 2-D CA which can synchronize m x n rectangular arrays in 2(m+n)-min((k+l-2), (m+n-k-l))-4 steps. The general is located on C_<kl>.
2001-11-14

B105 2次元セルラオートマトン上での同期アルゴリズム(ロジック,アルゴリズム)

スポンサーリンク

概要

著者

関連論文

スポンサーリンク