| 講演名 | 2008-10-14 Early Bird問題に関する一考察 谷邨 和久, 金澤 優, 上川 直紀, 梅尾 博司, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | セルラー・オートマトン(CA)は,John von Neumannによって考案された.CA上の問題の1つにRosenstiehl,Fiksel and Holliger[1973]によって提唱されたEarly Bird問題が存在する.Early Bird問題とはセル空間上で任意にリーダーを決定する遷移規則集合を求めるものである.この問題の解法として,最小の内部状態数5で動作するLegendi and Katona[1981]のアルゴリズムが知られている.しかし,Rosenstiehl,Fiksel and HolligerのアルゴリズムとLegendi and Katonaのアルゴリズムは詳細な遷移関数および時間計算量に関しては言及されていない.本稿ではLegendi and Katonaのアルゴリズムの不要な遷移規則を削減し,詳細な時間計算量の明らかにする.そして,Rosenstiehl,Fiksel and Holligerのアルゴリズムの実装を行う. |
| 抄録(英) | A model of cellular automata (CA) was devised for studying self-reproduction by John von Neumann. Early Bird Problem advocated to one of the problem on cellular space by Rosenstiehl, Fiksel and Holliger [1973] exists. Early Bird Problem is the one to obtain transition rule set that arbitrarily decides the leader on the cellular space. Algorithm of Legendi and Katona that operates by minimum number of internal states 5 is know as method of this problem. However, neither the transition fanction nor time complexity are referred to algorithm of Rosenstiehl, Fiksel and Holliger nor algorithm of Legendi and Katona. In this paper,an unnecessary transition rule of algorithm of Legendi and Katona is reduced, and relation time complexity is clarified. And, algorithm of Rosenstiehl, Fiksel and Holliger implement. |
| キーワード(和) | セルラー・オートマトン / 時間計算量 / Early Bird問題 |
| キーワード(英) | cellular automata / Early Bird Problem / time complexity |
| 資料番号 | CAS2008-34,NLP2008-46 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NLP |
|---|---|
| 開催期間 | 2008/10/7(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Nonlinear Problems (NLP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Early Bird問題に関する一考察 |
| サブタイトル（和） | |
| タイトル（英） | A Note on Early Bird Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | セルラー・オートマトン / cellular automata |
| キーワード(2)（和/英） | 時間計算量 / Early Bird Problem |
| キーワード(3)（和/英） | Early Bird問題 / time complexity |
| 第 1 著者 氏名（和/英） | 谷邨 和久 / Kazuhisa TANIMURA |
| 第 1 著者 所属（和/英） | 大阪電気通信大学大学院工学研究科情報工学専攻 Osaka Electro-Communication Univ., Graduate School of Engineering |
| 第 2 著者 氏名（和/英） | 金澤 優 / Masaru KANAZAWA |
| 第 2 著者 所属（和/英） | 大阪電気通信大学大学院工学研究科情報工学専攻 Osaka Electro-Communication Univ., Graduate School of Engineering |
| 第 3 著者 氏名（和/英） | 上川 直紀 / Naoki KAMIKAWA |
| 第 3 著者 所属（和/英） | 大阪電気通信大学大学院工学研究科情報工学専攻 Osaka Electro-Communication Univ., Graduate School of Engineering |
| 第 4 著者 氏名（和/英） | 梅尾 博司 / Hiroshi UMEO |
| 第 4 著者 所属（和/英） | 大阪電気通信大学大学院工学研究科情報工学専攻 Osaka Electro-Communication Univ., Graduate School of Engineering |
| 発表年月日 | 2008-10-14 |
| 資料番号 | CAS2008-34,NLP2008-46 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | 240 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |