文脈を用いない挿入・削除システムの計算能力
スポンサーリンク
概要
- 論文の詳細を見る
文献[1]で初めて導入された挿入・削除システムは, 挿入と削除の操作を基にしたDNA計算の理論的な計算モデルである.挿入の操作と削除の操作の両方が使えると計算能力は予想通り非常に高くなる.事実, 非常に制限された挿入・削除システムでさえ帰納的可算集合を特性化できることが示されている[1]〜[4].本稿では, 挿入・削除システムの計算能力について議論し, 挿入・削除システムでは文脈を全く用いなくても計算万能性を保存することを示す.
- 社団法人電子情報通信学会の論文
- 2005-06-17
著者
-
広瀬 貞樹
富山大学工学部
-
大川 知
会津大学コンピュータ理工学部
-
広瀬 貞樹
富山大学大学院理工学研究部
-
広瀬 貞樹
東北大学電気通信研究所
-
広瀬 貞樹
富山大学大学院理工学研究部:富山大学工学部知能情報工学科
-
広瀬 貞樹
富山大
-
広瀬 貞樹
富山大学
関連論文
- 不完全な同期下の単純セルオートマトンの時空間パターンによる分類(情報・システム基礎)
- Langtonの自己増殖ループの形態的進化
- Watson-Crickオートマトンの族の間の関係とそれらの族と文脈自由言語との関係
- 16セグメントディスプレイ上の英字パターンの一斉射撃問題
- 文脈を用いない挿入・削除システムの計算能力
- On a homomorphic characterization of the class of slender context-free languages (Languages, Algebra and Computer Systems)
- 線形言語の部分族と言語の特性化
- k-グラフ生成文法
- 点の次数3以下のグラフに対する2部グラフ化問題
- 7セグメントディスプレイ上の数字パターンの一斉射撃問題
- 推論の失敗を考慮した仮説推論システム(人工知能, 認知科学)
- 環境の変化によって生じる複雑な形をした雪の結晶の類似パターン生成
- CCDカメラ画像に基づいた自動車の車庫入れの自動化(高度交通システム(ITS))
- 打鍵間時間を基にした認証システムのリズム打鍵による改善(ネットワークセキュリティ)(コラボレーションアートとネットワークエンターテイメント)
- 改良山登り法によるコストに基づく仮説推論の高速最適解法
- クラスタリングによる人間の振舞い認知
- 赤外線センサ情報からのデータマイニングによる独居老人の振舞い認知に関する一考察
- 動的環境に対処するための遺伝的アルゴリズムの制御方法
- 故障診断のための事例ベース推論を導入した高速仮説推論システム
- 実時間探索を導入したコストに基づく仮説推論システムにおけるヒューリスティック関数の改良
- 複数の人間の家庭内における振舞い認知 (特集 知的センシング技術と設備管理)
- 仮説推論に対する3種の近似解法
- 述語論理知識を扱う全解探索仮説推論の高速化
- 北陸支部 : 表彰活動による学生の元気付け(わが支部の魅力はここにあり)
- 歩行者の安全を考慮した交通信号制御に関する研究
- 万能文法と言語の代数的表現 (計算の複雑性に関する研究)
- 万能文法に関する二,三の考察
- 6-214 理論と実践の融合による社会人基礎力育成と目に見える評価システムの構築(口頭発表論文,(20)産学連携教育-II)
- 6-212 「製品開発体験実習による実践的ものづくり技術者育成」事業の活動報告(口頭発表論文,(20)産学連携教育-II)
- A-17-21 地上解像度にスケーラブルな雪ハザードマップの構築(A-17.ITS,一般セッション)
- 2-217 製品開発体験実習による実践的ものづくり技術者育成((18)産学連携教育-I,口頭発表論文)
- 癒し型ペットロボットの飼い主判別機構の実現
- セルオートマトンを用いた雪の結晶の類似パターン生成
- 仮説推論における累積実行時間の削減方法の提案
- 複数パターンの文字列照合におけるマッチングマシンの動的構成法
- 推論パスネットワークによる仮説合成時の無矛盾性チェックの改善案
- 最小スケルトン検索アルゴリズム
- 一般形状6面体辺要素を用いた有限要素電磁界解析
- KICK-SHOTGANとKICK-HOPEの実行比較
- プロダクションシステムのためのベリフィケーションシステムの構築
- 各種直積インスタンシエーション表現法の効用比較
- プロダクションシステムの直接条件照合アルゴリズムの改善案
- 推論パスネットワークによる仮説合成時の包摂処理の改善案
- 推論パスネットワークによる仮説推論の高速包摂処理
- 推論パスネットワークによる仮説推論における矛盾処理の効率改善
- ライフゲームの挙動におけるセル数依存性
- 409 産学連携による実践型ものづくり科目「製品開発体験実習」(OS14-1 ものづくり技術教育,オーガナイズドセッション:14 技術と社会(高等教育改善))
- 408 産学連携教育による実践的ものづくり技術者育成(OS14-1 ものづくり技術教育,オーガナイズドセッション:14 技術と社会(高等教育改善))
- ライフゲームにおける過渡現象のセル数依存性
- 仮説推論の反復に対する高速化
- 強化学習型マルチエージェントによる交通信号制御
- 条件照合アルゴリズムの動的双方向切換えを導入した高速プロダクションシステム
- 推論パスネットワークによる仮説推論の高速矛盾処理
- 命題論理の仮説推論に対する問題分割法の実行時間予測
- プロダクションシステムの高コストルール対処法 : 属性値管理
- MGTPによる仮説推論の改善案
- プロダクションシステムにおけるジョイン演算の順序に関する一考察
- 強化学習型マルチエージェントによる交通信号制御
- ライフゲームにおける過渡現象のセル数依存性
- 条件照合アルゴリズムの動的切り替えによるプロダクションシステムの高速化
- 高次αメモリを導入した直接条件照合アルゴリズム
- マルチエージェントシステムを用いたエレベータ群管理システム
- エレベータ群管理システムに対する一考察
- 述語論理知識を扱う全解探索仮説推論の高速化
- 環境の変化によって生じる複雑な形をした雪の結晶の類似パターン生成
- A-023 Pattern Generation on Two Dimensional Cellular Automata
- Pattern Generation on Two Dimensional Cellular Arrays (代数系アルゴリズムと言語および計算理論--RIMS研究集会報告集)
- The Competitiveness of Diversified Investment on Portfolio Selection Problem (New Developments of Theory of Computation and Algorithms)
- 推論パスネットワークによる仮説合成時の無矛盾性チェックの改善案
- 理科離れと工学の復権
- スペクトル解析による1次元セルオートマトンの分類
- 散逸境界条件下のセルオートマトンについて
- スペクトル解析による1次セルオートマンの分類
- 六方非対称な雪の結晶の類似パターン生成(研究速報)
- ICカード学生証・身分証で変わる大学
- 六方非対称な雪の結晶の類似パターン生成