講演抄録/キーワード |
講演名 |
2008-10-14 11:15
Early Bird問題に関する一考察 ○谷邨和久・金澤 優・上川直紀・梅尾博司(阪電通大) CAS2008-34 NLP2008-46 |
抄録 |
(和) |
セルラー・オートマトン(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 minimumnumber 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 / time complexity / Early Bird Problem / / / / / |
文献情報 |
信学技報, vol. 108, no. 240, NLP2008-46, pp. 1-6, 2008年10月. |
資料番号 |
NLP2008-46 |
発行日 |
2008-10-07 (CAS, NLP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
CAS2008-34 NLP2008-46 |
|