一変数テーブル参照による保存的セル・オートマトンの論理万能性
スポンサーリンク
概要
- 論文の詳細を見る
保存的セル・オートマトン(NCCA)は各セルの状態が整数値で表され,セルの総和が常に一定であるようなセル・オートマトン(CA)である.これは物理的な質量やエネルギーの保存性のある種のモデル化と考えることができる.45度反転対称ノイマン近傍NCCAの遷移規則は2変数関数の線形結合で表せることが知られており,その結果を用いて論理万能なNCCAが構成されている.本論文では2変数関数が二つのセルの値の差のみに依存する一変数関数の場合にも論理万能なNCCAを構成できることを示す.
- 一般社団法人情報処理学会の論文
- 2003-09-19
著者
-
森田 憲一
広島大学工学研究科
-
岩本 宙造
広島大学大学院工学研究科
-
森田 憲一
広島大学大学院工学研究科
-
岩本 宙造
広島大学工学研究科
-
岩本 宙造
広島大学大学院工学研究科・情報工学専攻
-
今井 克暢
広島大学大学院 工学研究科
-
今井 克暢
広島大学工学研究科
-
伊ヶ崎 明彦
広島大学大学院工学研究科
-
今井 克暢
広島大学工学研究院
関連論文
- 非決定性チューリング機械の厳密な領域階層定理 (画像符号化・映像メディア処理レター特集)
- 万能可逆チューリング機械の一構成法 (計算機科学基礎理論とその応用)
- A note on tatami tilings (アルゴリズムと計算機科学の数理的基盤とその応用--RIMS研究集会報告集)
- 非決定性チューリング機械の厳密な領域階層定理(情報・システム基礎)
- 4状態可逆チューリング機械の構成法 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- A-6-6 有限可逆セルオートマトンの軌道(A-6.情報理論,一般セッション)
- 単純な非同期論理素子による同期可逆セルオートマトンの構成法(オートマトン・言語理論)
- 同期可逆セルオートマトンを実現できる非同期セル空間
- 単純な非同期論理素子による同期可逆セルオートマトンの構成法
- 非同期セル空間における順序機械構成
- 自己参照メカニズムに基づく自己増殖セルオートマトンのシミュレーション(ディジタルデータ付き論文特集)
- 計算万能な81状態保存的可逆セルオートマトン(ディジタルデータ付き論文特集)
- 交代性計算によるセルオートマトンの加速
- 1次元可逆セル・オートマトンにおける線形加速
- 可逆的・保存的2次元セル空間への単純なコンピュータの埋め込み
- 6角形状可逆セル・オートマトンの万能性
- 1次元Number-Conserving可逆セル・オートマトンの計算万能性
- 32状態可逆セルオートマトン上での論理回路合成
- 計算万能な2次元8状態3角形状可逆セル・オートマトン
- RS型ベクトル機械上での幾つかの具体的問題に対するアルゴリズム
- 段数を制限したドミノタイリングの効率良い再構成アルゴリズム(アルゴリズム理論)
- (5)実験教育におけるコンピュータの有効利用 : 広島大学工学部計数管理工学講座での実施例(第2セッション 教育システム(II))
- 計算万能性を有する単純な1次元可逆セルオートマトン(代数、言語、計算システムにおけるアルゴリズム問題)
- 3入出力2状態可逆論理素子の万能性 : ロータリー素子の直接的構成法(計算理論とアルゴリズムの新展開)
- 計算万能な双曲セル・オートマトンについて (計算機科学基礎理論とその応用)
- 非同期セル空間における順序機械構成 (計算機科学基礎理論とその応用)
- 縮退していない2状態3記号可逆論理素子はすべて万能である
- 非同期セル空間における論理回路構成 (計算機科学基礎理論の新展開)
- 一変数テーブル参照による保存的セル・オートマトンの論理万能性
- 一意解析可能アレー文法による単連結図形及び単純閉曲線の生成(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- A101 3次元可逆セル空間における自己増殖と形態形成(形態形成関連)
- 一意解析可能アレイ文法による単連結図形及び単純閉曲線の生成 (計算理論とアルゴリズムの新展開)
- Simulation of One-Dimensional Cellular Automata by Uniquely Parallel Parsable Grammars (New Developments of Theory of Computation and Algorithms)
- Semi-Right-Terminating 一意解析可能文法による決定性文脈自由言語族の特徴付け (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 決定性Chomsky階層を成す一意解析可能文法族の標準形
- 一意解析可能Semi-Right-Terminating文法による決定性文脈自由言語族の特徴づけ
- Semi-Right-Terminating : 一意解析可能文法による決定性文脈自由言語族の特徴付け
- 一意並列解析可能ユニフィケーション文法 (計算モデルとアルゴリズム)
- Semi-Right-Terminating一意解析可能文法による決定性文脈自由言語族の特徴付け
- Uniquely Parsable Grammars
- 一意解析可能文法
- 3次元可逆自己増殖セル・オートマトンについて (計算モデルとアルゴリズム)
- 名辞論理体系に基づく自然言語文に対する推論法 : 日本語質疑応答システムへの応用
- Number conservingなセル空間での自己増殖 (計算理論とアルゴリズムの新展開)
- 3次元一意解析可能アレイ文法による図形の生成と認識について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 可逆コンピューティングのための新しい万能論理素子
- 2点スプライシングシステムの言語生成能力の万能性(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- 可逆的・保存的なセル・オートマンの計算能力 (言語,代数系および計算機システム)
- Two-Point Splicing Systemの言語生成能力の万能性 (計算モデルとアルゴリズム)
- 一意解析可能ユニフィケーション文法について
- 一意解析可能文法とその自然言語解析への応用
- 非決定性回路族における深さと非決定性ゲート数の関係
- Universality of Reversible Logic Elements with 1-Bit Memory : Extended Abstract (Mathematical Foundations and Applications of Computer Science and Algorithms)
- センサネットワーク上の群生成による情報伝達 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 差分法の任意形状格子メッシュへの適用に関する検討
- テープ記号数を制限したチューリング機械の領域階層
- 総合電機メーカにみる戦後50年の技術変遷と景気変動の影響
- テープ記号数を制限した決定性TMと交代性TMの領域計算量について
- CRCW PRAMの時間計算量の稠密な階層
- 並列計算用に拡張したTMの時間計算量の階層
- チューリング機械の領域計算量の厳密な階層について(計算理論とその応用)
- テープ記号数を制限した領域限定TMの階層について
- 2次元可逆セル・オートマトンにおける一斉射撃問題(計算モデルと計算の複雑さに関する研究)
- 確率的手法によるCRCW PRAM間の模倣について
- 計算万能な2次元8状態3角形状可逆セル・オートマン(計算理論とその応用)
- 1次元可逆セル・オートマトンにおける一斉射撃問題の高速解(アルゴリズムと計算量理論)
- 1次元可逆セル・オートマトンにおける一斉射撃問題について(計算量理論)
- 1次元可逆セル・オートマトンにおける一斉射撃問題について
- 1次元可逆セル・オートマトンにおける一斉射撃問題について
- 決定性プッシュダウン・オートマトンおよび有限オートマトンと等価な一意解析可能文法(UPG)のサブクラス
- ランダムアクセス機能を持つ並列TMの時間計算量の階層
- PRAMおよび対数時間一様な論理回路族に基づく計算量の階層(計算モデルと計算の複雑さに関する研究)
- $\alpha$連結成分問題の計算複雑さの上昇について(計算量理論)
- On Parallelizability of α-Connectivity
- 並列化が徐々に困難になるグラフ問題について
- 色塗り分け問題がP完全又はNCになる為の十分条件について(理論計算機科学とその周辺)
- 組合せ問題に対する RS 型ベクトルアルゴリズム
- RS型ベクトル機械の実際的応用の可能性について(計算および計算量理論とその周辺)
- 可逆コンピューティング : ビリヤードボールでコンピュータが作れるか?
- 記憶付き可逆論理素子の能力の階層構造について (アルゴリズムと計算理論の新展開)
- 多面体テラインの面警備員数の上下限の改善(研究速報)
- Reversible multi-head finite automata and space-bounded Turing machines (New Trends in Theoretical Computer Science)