3次元セルラーオートマトン上での一斉射撃アルゴリズムの設計

摘要

The firing squad synchronization problem on cellular automata has been studied extensively for morernthan forty years, and a rich variety of synchronization algorithms have been proposed. In the present paper, we givernan algorithm can synchronize any three-dimensional array of size m × n × ℓ in optimum m + n + ℓ+max(m, n,ℓ) - 4rnsteps.%セルラーオートマトン上における一斉射撃問題は40年以上にわたり研究されている．1次元及び2次元セルラーオートマトンは数多くのアルゴリズムが知られているが，3次元セルラーオートマトンに関しては考案されているアルゴリズムは多くはない．本稿では，サイズm×n×ℓの3次元セルラーオートマトンを最適時間である，m＋n＋ℓ+max（m，n，ℓ）-4ステップで同期させるアルゴリズムを提案する.