| 講演名 | 2011-10-20 2次元セルラ・オートマトン上の一斉射撃問題に関する研究 野村 輝, 内野 博貴, 梅尾 博司, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 並列計算機モデルの1つとしてセルラ・オートマトンの同期問題として一斉射撃問題が知られている.一斉射撃問題は1957年J. Myhillにより提唱され,これまで数多くの研究がされてきた.この中で1次元セルラ・オートマトン,2次元セルラ・オートマトン上での一斉射撃問題のアルゴリズムの設計・実装は盛んに行われてきた.近年,1次元セルラ・オートマトン上の一斉射撃問題のアルゴリズムとして片側分割法が提案された.本稿では,片側分割法を用いた2次元正方形セルラ・オートマトン上での一斉射撃問題のアルゴリズムを提案する.また,そのアルゴリズムを用い,2次元長方形セルラ・オートマトン,3次元立方体セルラ・オートマトン上での一斉射撃問題のアルゴリズムの設計を行う. |
| 抄録(英) | The firing squad synchronization problem (FSSP, for short) on cellular automata has been studied extensively for more than fifty years, and a rich variety of synchronization algorithms have been proposed for one- and two-dimensional cellular automata. In the present paper, we propose a new optimum-time FSSP algorithm for two-dimensional square cellular automata. The algorithm can synchronize any square arrays of size n×n with a general at one corner at exactly 2n-2 steps. It is based on a new technique called one-sided recursive halving marking and is quite different from the well known classical FSSP algorithm proposed by Beyer [1969] and Shinahr [1974]. |
| キーワード(和) | セルラ・オートマトン / 一斉射撃問題 |
| キーワード(英) | cellular automaton / FSSP / square synchronization |
| 資料番号 | CAS2011-36,NLP2011-63 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NLP |
|---|---|
| 開催期間 | 2011/10/13(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Nonlinear Problems (NLP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 2次元セルラ・オートマトン上の一斉射撃問題に関する研究 |
| サブタイトル（和） | |
| タイトル（英） | A Study on Two-Dimensional FSSP Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | セルラ・オートマトン / cellular automaton |
| キーワード(2)（和/英） | 一斉射撃問題 / FSSP |
| 第 1 著者 氏名（和/英） | 野村 輝 / Akira NOMURA |
| 第 1 著者 所属（和/英） | 大阪電気通信大学 Osaka Electro-Communication University |
| 第 2 著者 氏名（和/英） | 内野 博貴 / Hiroki UCHINO |
| 第 2 著者 所属（和/英） | 大阪電気通信大学 Osaka Electro-Communication University |
| 第 3 著者 氏名（和/英） | 梅尾 博司 / Hiroshi UMEO |
| 第 3 著者 所属（和/英） | 大阪電気通信大学 Osaka Electro-Communication University |
| 発表年月日 | 2011-10-20 |
| 資料番号 | CAS2011-36,NLP2011-63 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | 243 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |