1 ビット・セルラオートマトンにおける最適時間一斉射撃アルゴリズムの実現

• Item type: SIG Technical Reports(1)
• 公開日: 2002-11-08
• タイトル: 1 ビット・セルラオートマトンにおける最適時間一斉射撃アルゴリズムの実現
• タイトル / 言語: en
• タイトル: A Realization of Optimum - Time Firing Squad Synchronization Algorithm on 1 - Bit Cellular Automaton
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 株式会社メガチップス
• 著者所属: 株式会社インターネットイニシアティブ
• 著者所属: 大阪電気通信大学総合情報学部情報工学科大阪電気通信大学大学院情報工学専攻
• 著者所属(英): en
• 著者所属(英): MegaChips Co., LTD.
• 著者所属(英): en
• 著者所属(英): Internet Initiative Japan Inc.,
• 著者所属(英): en
• 著者所属(英): Osaka Electro - Communication Univ., Faculty of Information Science and Technology, Osaka Electro-Communication Univ., Graduate School of Engineering
• 著者名: 西村, 順; 曽我部, 崇; 梅尾, 博司
• 著者名(英): Jun, Nishimura; Takashi, Sogabe; Hiroshi, Umeo
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: n 個のセルからなるセル空間の同期を2n - 2 ステップの最適時間で実現するセルラ・オートマトン(CA)は従来から数多く提案されている．これらのセルラ・オートマトンにおいて，隣接するセル間の1 ステップ当たりの通信量はO(1)ビットであるが，セル間通信量は有限状態記述というオートマトンの定義には明示的に現れず，セル間通信量に関する研究はこれまであまりなされていない．本稿では，1 ステップあたりのセル間通信量を1 ビットに制限したセルラ・オートマトン・モデルCA1-bit を定義し，CA1-bit 上で最適時間で動作する一斉射撃アルゴリズムを提案する．我々のアルゴリズムは，すでに正当性が示されているWaksman のアルゴリズム[7 8](セル間通信量はO(1)ビットである)をベースとしており，セルの内部状態数は78 ，遷移規則数は208 である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In the long history of the study of cellular automata, the amounts of bit-information exchanged at one step between neighboring cells have been assumed to be O(1)-bit. In this paper we introduce a new class of cellular automata, CA1-bit, whose inter-cell communication is restricted to 1-bit and propose an optimum-time (2n -2)-step firing squad synchronization algorithms for n cells on CA1-bit. The number of internal states in each cell is 78 and the total number of transition rules is 208. The algorithm we propose is based on Waksman’s optimum-time algorithm which has been shown valid for any n.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2002, 号 103(2002-AL-087), p. 59-66, 発行日 2002-11-08
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会