一斉射撃問題の時間計算量に関する一考察

カテゴリ: 全国大会

論文No: 3-026

グループ名: 【全国大会】平成22年電気学会全国大会論文集

発行日: 2010/03/05

タイトル(英語): A Note on Synchronization Steps in Firing Squad Synchronization Problem

著者名: 野村 輝(大阪電気通信大学),Jean-Baptiste Yunes (Universite Paris 7 Denis Diderot),梅尾 博司(大阪電気通信大学)

著者名(英語): Akira Nomura(Univ. Osaka Electro-Communication),Jean-Baptiste Yunes(LIAFA - Universite Paris 7 Denis Diderot),Hiroshi Umeo(Univ. Osaka Electro-Communication)

キーワード: セルラ・オートマトン|一斉射撃問題

要約(日本語): セルラ・オートマトンを同期させる問題として、一斉射撃問題が知られている。一斉射撃問題は1964年にMyhillによって提唱されて以来、数多くの研究がされている。 一斉射撃問題の最適時間は1次元上に並べられたセルの数をnとすると2n-2ということが知られている。本研究では一斉射撃問題での同期時間を大幅に遅らせるアルゴリズムを提案し、それを実装する。今まで一斉射撃問題は最適時間や線形時間で研究が行われてきた。そこで、次のような疑問を持った。・どのような時間でセルラ・オートマトンを同期させることができるのか？・線形時間を大幅に遅らせることはできるのか？

原稿種別: 日本語

PDFファイルサイズ: 1,468 Kバイト