2次元アレイ上での最適時間一斉射撃アルゴリズムの設計

摘要

セルラーオートマトンに対する同期問題は,一斉射撃問題と呼ばれ,これまでに数多くの研究が行われている.2次元セル空間に対する一斉射撃アルゴリズムの設計例は,1次元アレイと比較して非常に少ない.2次元長方形アレイ上での一斉射撃アルゴリズムとして,Shinahr10 が28状態の最適時間アルゴリズムを,Maeda, Michisaka and Umeo18らは14状態の最適時間アルゴリズムを設計している.本稿では状態数を12に削減した最適時間アルゴリズムを提案する.ここで述べる最適時間アルゴリズムは,サイズがm ×nの長方形アレイに対して,m＋n＋max(m,n)－3ステップで動作する.