モノイドプログラムによる論理回路計算量クラスの構造解析
スポンサーリンク
概要
- 論文の詳細を見る
論理回路に基づいて定義された様々な計算量クラスがモノイドプログラムと呼ばれる計算モデルを通して代数的に特徴付けられている.モノイドプログラムの研究は端緒についたばかりであり十分な成果が上がっているとはいい難いが,回路計算量(サイズや段数)を分析するための新たな方向を提示していると思われる.本稿では,モノイドプログラムに関連した論理回路計算量クラスに関する既知の結果と未解決の諸問題を解説する.
- 一般社団法人電子情報通信学会の論文
- 1996-03-11
著者
関連論文
- 2部グラフの部分クラスに対するGI完全性について
- グラフ同型写像の数え上げ問題に対するアルゴリズムについて
- グラフ同型写像の数え上げ問題に対するアルゴリズムについて
- グラフ同型写像の数え上げ問題に対するアルゴリズム
- 行列集合の自己同型群を求めるための動的計画アルゴリズム
- コーダルグラフに関する同型性判定のための単純なアルゴリズム
- 小さな単体成分からなるコーダルグラフの自己同型群を求めるためのアルゴリズム
- 区間グラフの認識アルゴリズムについて
- 到達可能性判定問題の計算量について
- 到達可能性判定問題の計算量について(縮約版) (アルゴリズムと計算の理論)
- 数え上げ計算モデルの計算能力について
- 数え上げ計算モデルの計算能力について
- グラフ同型性判定問題の計算量
- グラフ同型性判定問題の計算量(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- 解の個数を数えることの複雑さについて : 数え上げ問題の計算量
- 正則言語による論理関数の計算量解析 : 群の上で動作するモノイドプログラムについて (離散的アルゴリズムと計算量)
- 正則言語による論理関数の計算量解析 : 群の上で動作するモノイドプログラムについて
- モノイドプログラムによる論理回路計算量クラスの構造解析