| 講演名 | 2001/4/9 交代性計算によるセルオートマトンの加速 岩本 宙造, 立石 勝之, 森田 憲一, 今井 克暢, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | セルオートマトンには,二つの単純なモデルがある.一つは,セルの半無限配列であり,イテラティブアレイ(iterative array, IA)と呼ばれる.もう一つは,n個のセルの有限配列であり,限定セルアレイ(bounded cellular array, BCA)と呼ばれる.本稿では,交代性計算を利用して,IAに対する二次的加速定理とBCAに対する指数的加速定理を示す.(i)任意の計算可能関数s(n),t(n)≥nに対し,s(n)t(n)時間の決定性IAはO(s(n))領域O(t(n))時間の交代性IAで模倣できることを証明する.t(n)時間IAはt(n)領域限定なので,(t(n))^2時間決定性IAはO(t(n))時間交代性IAで模倣できる.このことから,O(t(n))時間のいかなる決定性IAでもLを受理できないが,O(t(n))時間の交代性IAではLを受理できる,という言語Lが存在することが導かれる.(ii)任意の計算可能関数t(n)に対し,t(n)時間の非決定性BCAは線形時間の交代性BCAで模倣できることを証明する. |
| 抄録(英) | There are two simple models of cellular automata: a semi-infinite array (with left boundary) of cells, called an iterative array(IA), and a finite array (delimited at both ends) of n cells, called a bounded cellular array(BCA). This paper presents a quadratic speedup theorem for IAs and an exponential speedup theorem for BCAs by using alternations. (i) It is shown that for any computable functions s(n), t(n)≥n, every s(n)t(n)-time deterministic IA can be simulated by an O(s(n))-space O(t(n))-time alternating IA. Since any t(n)-time IA is t(n)-space bounded, every (t(n))^2-time deterministic IA can be simulated by an O(t(n))-time alternating IA. This leads to a separation result: There is a language which can be accepted by an alternating IA in O(t(n)) time but not by any deterministic IA in O(t(n)) time. (ii) It is also shown that for any computable function t(n), every t(n)-time nondeterministic BCA can be simulated by a linear-time alternating BCA. |
| キーワード(和) | イテラティブアレイ / 限定セルアレイ / 交代性計算 / 加速定理 |
| キーワード(英) | Iterative array / bounded cellular array / alternating computation / speedup theorem |
| 資料番号 | COMP2001-1 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2001/4/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 交代性計算によるセルオートマトンの加速 |
| サブタイトル（和） | |
| タイトル（英） | Speeding-up Cellular Automata by Alternations |
| サブタイトル（和） | |
| キーワード(1)（和/英） | イテラティブアレイ / Iterative array |
| キーワード(2)（和/英） | 限定セルアレイ / bounded cellular array |
| キーワード(3)（和/英） | 交代性計算 / alternating computation |
| キーワード(4)（和/英） | 加速定理 / speedup theorem |
| 第 1 著者 氏名（和/英） | 岩本 宙造 / Chuzo IWAMOTO |
| 第 1 著者 所属（和/英） | 広島大学工学部 Faculty of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 立石 勝之 / Katsuyuki TATEISHI |
| 第 2 著者 所属（和/英） | 広島大学工学部 Faculty of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 森田 憲一 / Kenichi MORITA |
| 第 3 著者 所属（和/英） | 広島大学工学部 Faculty of Engineering, Hiroshima University |
| 第 4 著者 氏名（和/英） | 今井 克暢 / Katsunobu IMAI |
| 第 4 著者 所属（和/英） | 広島大学工学部 Faculty of Engineering, Hiroshima University |
| 発表年月日 | 2001/4/9 |
| 資料番号 | COMP2001-1 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 5 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |