2 次元セルラーオートマトンのための遷移関数の実現手法について

摘要

セルラーオートマトンと呼ばれる有限オートマトンの配列を同期させる問題は, 一斉射撃問題と呼ばれMyhill[1957] によって提唱された. 以来, 数多くの一斉射撃アルゴリズムが考案されてきた. Shinahr[1974] により考案されたアルゴリズムは, 世界で初の二次元セルラーオートマトンの同期に関するアルゴリズムである. また, Shinahr のアルゴリズムは以降の数多くの研究で用いられており非常に有用な物である. しかし, このアルゴリズムの遷移規則集合はワイルドカードを用いた561 種類の遷移規則からなり, 実際に使用される具体的な遷移規則は示されていない. さらに, ワイルドカードを用いた遷移規則には遷移規則の展開時に遷移規則の重複などの問題が生じる可能性がある. そこで, 本稿ではワイルドカードを含む遷移規則の展開手法を考案し, Shinahr の遷移規則集合の導出を行う.