単位時間あたりのセル間通信量を1ビットに制限した2次元セルラ・オートマトンによる2値図形の連結性判定のための線形時間アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
セルラ・オートマトンは網目結合を持つ並列計算モデルとして, また最近では複雑系, 人工生命などの分野で数多くの研究がなされているが, 隣接セル間の通信量に着目した研究はほとんどなされていない.本稿では, セル間通信量を1ビットに制限した2次元セルラ・オートマトンを定義し, 同モデル上で2次元2値図形の連結性判定のための線形時間アルゴリズムを示す.正確には, 単位時間あたりのセル間通信量を1ビットに制限した2次元セルラ・オートマトンは, サイズm×nの2値図形の連結性判定を2(m+n)ステップで実行可能であることを示す.セル間通信量を1ビットに制限した計算モデルは, セルラ・オートマトンはのなかでも最も計算能力が小さいモデルのひとつと考えられる.
- 社団法人電子情報通信学会の論文
- 1998-06-23
著者
-
梅尾 博司
大阪電気通信大学大学院工学研究科情報工学専攻
-
梅尾 博司
大阪電通大
-
梅尾 博司
大阪電気通信大学総合情報学部情報工学科:大阪電気通信大学大学院情報工学
-
稲田 真
大阪電気通信大学情報工学部
-
梅尾 博司
大阪電気通信大学
-
稲田 真
大阪電気通信大学大学院
関連論文
- 2次元リングアレイ上での最適時間一斉射撃アルゴリズムに関する考察
- セルオートマトン理論の再構築とNatural Computingへの応用
- Early Bird問題に関する一考察
- 1次元リング結合セルラーオートマトンのための4状態一斉射撃アルゴリズム
- 正方形アレイのための一般化一斉射撃アルゴリズムについて
- 1状態および2状態1ビット通信セルラ・オートマトンの数列生成能力について
- 3次元セルラーオートマトン上での一斉射撃アルゴリズムの設計(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- Balzerによる最適時間一斉射撃アルゴリズムの正当性について
- B105 2次元セルラオートマトン上での同期アルゴリズム(ロジック,アルゴリズム)
- B104 1ビットセルオートマトン上での数列生成問題(ロジック,アルゴリズム)
- 1方向再帰性を有する線形時間一斉射撃アルゴリズムの設計と実装
- A-12-3 1 方向再帰性を有する最適時間一斉射撃アルゴリズムの設計と実装
- Early Bird問題に関する一考察
- Balzerによる最適時間一斉射撃アルゴリズムの正当性について
- 1状態1ビット通信セルラ・オートマトンの数列生成能力について(光カオス,一般)
- 2状態1ビット通信セルラ・オートマトンで生成可能な2次多項式数列について
- 1ビット通信セルラ・オートマトン上での非正則数列生成アルゴリズムについて(セッション2)
- 2次元1ビット通信セルラーオートマトン上での最適時間一斉射撃アルゴリズムの設計(グラフ,ペトリ,ニューラルネット及び一般)
- 2次元1ビット通信セルラーオートマトン上での最適時間一斉射撃アルゴリズムの設計(グラフ,ペトリ,ニューラルネット及び一般)
- 1ビット通信セルラーオートマトン上での一斉射撃アルゴリズム
- 1ビット通信セルラーオートマトン上での素数列生成アルゴリズム
- 実時間数列生成アルゴリズムの1ビット通信セルラ・オートマトン上での実装について
- 有限要素法を用いた摩擦音発生時の声道内呼気流の推定
- 2次元セルラーオートマトン上での最適時間一斉射撃アルゴリズムの設計 (コンカレント工学)
- 2値図形の並列収縮アルゴリズムに関する考察
- 単位時間あたりのセル間通信量を1ビットに制限した2次元セルラ・オートマトンによる2値図形の連結性判定のための線形時間アルゴリズム
- 単位時間あたりのセル間通信量を1ビットに制限したセルラ・オートマトンによる数列の実時間生成と連結性判定アルゴリズム
- セル間通信量を1ビットに制限した2次元セルラ・オートマトンによる連結図形の線形時間認識について
- VPMT:分散メモリ型並列計算機のための並列プログラム可視化システム
- ハイパーキューブアルゴリズムの可視化に関する研究
- VPMT:分散メモリ型並列計算機のための並列プログラム可視化システム
- 星野 力 (著), "誰がどうやってコンピュータを創ったのか?", 共立出版, 158p, 2200円, 1995, ISBN4-320-02742-6
- セルラオートマトン
- VPMT : 分散メモリ型並列計算機のための並列プログラム可視化システム
- VPMT: 分散メモリ型並列計算機のための並列プログラム可視化システム
- 疎結合並列計算機上でのプロセッサ・ファームの効果的実装法
- 並列計算機(トランスピュータ・システム)における動作モニタの開発とその有効性
- トランスピュータ並列計算機による生物集団の行動パターンシミュレーション
- SIMD上の並列アルゴリズム (並列アルゴリズムの現状と動向)
- 小特集「並列アルゴリズムの現状と動向」の編集にあたって
- シストリック・アーキテクチャとそのアルゴリズム(パラレル・アルゴリズム)
- プレフィクス計算のための並列アルゴリズム (コンピュ-タと情報処理)
- ハイパ-キュ-ブ結合並列計算機上でのデ-タ・ル-ティング・アルゴリズム (コンピュ-タと情報処理)
- ブロードキャスト機能を備えた網目結合並列計算機のためのアルゴリズムに関する最近の研究
- 実時間シストリック・コンボルバの設計について
- シストリック・アレイによる線形時間限定セルラ・オ-トマンの模倣
- 1ビット・セルラオートマトンにおける最適時間一斉射撃アルゴリズムの実現
- 最適時間一斉射撃アルゴリズムの1ビット・セルラ・オートマトン上での実現
- 一斉射撃を用いた並列・データ・ルーティング・アルゴリズム
- Waksmanの一斉射撃アルゴリズムに対する最適化遷移規則集合の正当性について
- A.Waksmanの一斉射撃アルゴリズムに関する一考察
- A. Waksmanの一斉射撃アルゴリズムに関する一考察
- 2次元正方形アレイ上での最適時間一斉射撃アルゴリズムの設計
- D-1-10 2次元セルラーオートマトン上での最適時間一般化一斉射撃アルゴリズムの設計(D-1. コンピュテーション)
- D-1-9 2次元最適時間一斉射撃アルゴリズムの実装について(D-1. コンピュテーション)
- 2次元アレイ上での最適時間一斉射撃アルゴリズムの設計
- 2次元アレイ上での最適時間一斉射撃アルゴリズムの設計
- 多将軍一斉射撃問題について
- 一斉射撃問題の一般化に関する考察
- 2次元長方形セルラーオートマトン上での最適時間一斉射撃アルゴリズムの設計と実装
- 2次元一斉射撃アルゴリズムのための新しい設計手法
- 2次元一般化一斉射撃アルゴリズムについて
- 2次元セルラオートマトン上での一斉射撃アルゴリズム
- D-1-1 2次元セルラオートマトン上での一般化一斉射撃アルゴリズムの設計と実装
- 6 状態 3n ステップ一斉射撃アルゴリズムの設計と実装
- パラレルプログラミングを始めてみませんか(番外編)可視化情報を用いた並列アルゴリズム教育の試み
- 繰り返し論理回路による高速数列生成アルゴリズム
- ピラミッド・コンピュ-タに関する最近の研究
- 2次元リングアレイ上での最適時間一斉射撃アルゴリズムに関する考察
- 3次元セルラーオートマトン上での一斉射撃アルゴリズムの設計(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 3次元セルラーオートマトン上での一斉射撃アルゴリズムの設計(理論,回路,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- A-009 正方形一斉射撃アルゴリズムの実現に関する考察(A分野:モデル・アルゴリズム・プログラミング)
- 遷移規則変換に基づく三角形セルラーオートマトンのための同期プロトコルの設計について (テーマ:知能・適応と社会,ネットワーク) -- (ネットワーク・WWW)
- 2次元セルラーオートマトン上における最適時間一斉射撃アルゴリズムの設計(グラフ,ペトリ,ニューラルネット及び一般)
- 2次元セルラーオートマトン上における最適時間一斉射撃アルゴリズムの設計(グラフ,ペトリ,ニューラルネット及び一般)
- シストリック計算幾何アルゴリズムに関する最近の研究
- 2次元セルラーオートマトン上における最適時間一斉射撃アルゴリズムの設計と実装
- マルチビット最適時間一斉射撃アルゴリズムの設計(NLP一般)
- A-12-7 通信量を1ビットに制限した小さな自己複製セルラーオートマトンの構成(A-12.コンカレント工学,一般セッション)
- 2次元セルラーオートマトン上での最適時間一斉射撃アルゴリズムの設計(一般,コンカレントシステム及び一般)
- セルラーオートマトン上での耐故障性自己増殖モデルの設計
- 1ビット通信セルラーオートマトン上での自己増殖機能の実現
- 最適実時間シストリック・多項式除算アルゴリズム
- シストリック・アレイ
- 分割統治法に基づいた線形時間・画像連結要素ラベリング・アルゴリズム
- セルラ計算機のための最適時間・並列アドレス設定アルゴリズム
- パイプイン・アドレス設定法
- シストリック・アレイにより模倣可能なSIMD並列計算機のあるクラス
- 状態変化回数を1回に限定したセルラオートマトンと有限オートマトンとの等能力性
- 2次元セルラ・オートマトン上の一斉射撃問題に関する研究
- 2次元セルラ・オートマトン上の一斉射撃問題に関する研究
- 2次元セルラ・オートマトン上の一斉射撃問題に関する研究
- 多次元最適時間FSSPアルゴリズム
- 2次元最適時間同期アルゴリズム
- 多次元最適時間FSSPアルゴリズム
- ゼブラマッピングを利用した2次元一斉射撃アルゴリズムの実装(学生セッション)