代入制約付き構文的単一化問題の計算量
スポンサーリンク
概要
- 論文の詳細を見る
現実の世界では,暗号を用いたプロトコルの安全性検証問題のように,限られた情報・限られた操作のみを用いてゴールが達成可能か否かが問題となるケースが多々ある.単一化問題の自然な拡張である代入制約付き単一化間題を用いれば,この種の問題を自然に記述することができる.本稿では、代入制約付き単一化問題の基礎となる,代入制約付き構文的単一化問題(以下SUPCSと略記)について議論する.著者らは既に,SUPCSは一般には決定不能であること,利用可能な項として線形なものだけを考えれば,同問題が決定可能となることを示している.本稿では,利用可能な項が線形または閉じているとの仮定の下で,同問題の計算量について議論する.
- 社団法人電子情報通信学会の論文
- 1996-03-11
著者
関連論文
- 光バースト交換網における誤り訂正符号を用いたバースト生成方式の伝送遅延評価
- アドホックなセンサネットワークを考慮したグループ鍵管理方式の提案と評価(無線分散ネットワーク,一般)
- 大規模センサネットワークに適したサーバデータ認証方式(ユビキタス・センサネットワークの要素技術,コンテクストの抽出,スマートスペース,ユビキタス生活支援,一般)
- 私の研究遍歴(その3)
- 私の研究遍歴(その2)嵩忠雄
- 私の研究遍歴(1)
- 準最適な最小距離探索を用いて計算複雑度を削減した繰り返し復号法(モバイル環境におけるPerson to Person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- 準最適な最小距離探索を用いて計算複雑度を削減した繰り返し復号法(モバイル環境におけるPerson to person高信頼性情報流通技術 : 情報通信サブソサイエティ合同研究会)
- 準最適な最小距離探索を用いて計算複雑度を削減した繰り返し復号法(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- 準最適な最小距離探索を用いて計算複雑度を削減した繰り返し復号法(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- トップ・ダウン方式の再帰的最小重み探索を用いた軟判定繰り返し復号法
- トップ・ダウン方式の再帰的最小重み探索を用いた軟判定繰り返し復号法
- トップ・ダウン方式の再帰的最小重み探索を用いた軟判定繰り返し復号法
- トップ・ダウン方式の再帰的最小重み探索を用いた軟判定繰り返し復号法
- 最小重みトレリス線図探索のリスト復号を用いた新しい軟判定繰り返し復号法
- 最小重みトレリス線図探索のリスト復号を用いた新しい軟判定繰り返し復号法
- 最小重みトレリス線図探索のリスト復号を用いた新しい軟判定繰り返し復号法
- 最小重みトレリス線図探索のリスト復号を用いた新しい軟判定繰り返し復号法
- 加重サンプリングを用いたブロック符号の復号誤り確率の評価法
- 加重サンプリングを用いたブロック符号の復号誤り確率の評価法
- 加重サンプリングを用いたブロック符号の復号誤り確率の評価法
- ビット毎に誤り率が異なるMISRのエイリアス確率と完全重み分布
- ビット毎に誤り率が異なるMISRのエイリアス確率と完全重み分布
- Sum-Product復号法の演算量削減法の提案
- 確率多重文脈自由文法によるRNAシュードノット構造予測(DNA・タンパク質構造)
- RNA2次構造記述向き形式文法の生成能力について(文字列アルゴリズム)
- 通信プロトコルのフェーズ連結法とそれに基づく検証法
- VAR-CCGの生成能力について
- 語彙機能文法のいくつかの部分クラスに対する一般認識問題の計算量について
- 自然語仕様から代数的仕様への変換における表現式の構文規則の生成
- メソッドスキーマにおける型整合性の解析アルゴリズム
- 有界到達可能性解析を用いた非有界通信プロトコルの解析法
- 自然語仕様から代数的仕様への変換における辞書項目生成の支援
- 拡張有限状態機械でモデル化したOSIセションプロトコルの検証
- リード・マラー符号の最小重み部分符号語集合の構造を用いた軟値入出力復号法のシミュレーション結果(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- リード・マラー符号の最小重み部分符号語集合の構造を用いた軟値入出力復号法のシミュレーション結果(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- リード・マラー符号の最小重み部分符号語集合の構造を用いた軟値入出力復号法のシミュレーション結果(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 適応型再帰的最尤復号法の実装とシミュレーション結果(一般,フレッシュマン,招待講演)
- 2元線形符号の最粗な並列・連接形剰余類への分解法に基づく適応的再帰形最尤復号法(モバイル環境におけるPerson to Person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- 2元線形符号の最粗な並列・連接形剰余類への分解法に基づく適応的再帰形最尤復号法(モバイル環境におけるPerson to person高信頼性情報流通技術 : 情報通信サブソサイエティ合同研究会)
- 2元線形符号の最粗な並列・連接形剰余類への分解法に基づく適応的再帰形最尤復号法(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- 2元線形符号の最粗な並列・連接形剰余類への分解法に基づく適応的再帰形最尤復号法(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- ハークレート符号に対する順序統計量を利用した再帰的最尤復号法
- 順序統計量を利用した再帰的最尤復号法
- 順序統計量を利用した再帰的最尤復号法
- 順序統計量を利用した再帰的最尤復号法
- 有界重なり項書換え系と構成的正則保存性
- 順序ソート付き単一化問題を解くための手続き : 左非線形システムへの対応
- 軟値入出力逐次型限界距離復号法について(モバイル環境におけるPerson to Person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- 軟値入出力逐次型限界距離復号法について(モバイル環境におけるPerson to person高信頼性情報流通技術 : 情報通信サブソサイエティ合同研究会)
- 軟値入出力逐次型限界距離復号法について(モバイル環境におけるPerson to person高信頼性情報流通技術)(情報通信サブソサイエティ合同研究会)
- 暗号技術が利用できない環境において閲覧履歴保護を実現するHTTPサーバの機能拡張
- 通信量を考慮したサーバの不正行為も防止する電子透かしシステム
- 多値画像情報における視覚的秘密共有を用いたデジタル透かし技法
- 営為としての研究について
- ディジタル動画像に対する著作権保護の一手法 : 不正コピーを行ったユーザを特定する手法
- ディジタル図書館のための概念情報を用いた科学技術論文の検索手法
- パスワード事前宣言による個人認証法 : 磁気力ードを用いた安全な個人認証法
- 曼陀羅図書館の構築の試み
- 大学附属図書館電子化の試み
- 大学院における情報処理教育の一つの取組み : 奈良先端科学技術大学院大学を例として ( 情報処理最前線)
- ランダマイズ10進2進変換テーブルを用いた擬似乱数生成法の改良とその評価
- SFA-LDPC符号における符号化率と性能の関係について(LDPC符号セッション,LDPC符号,一般)
- セクショントレリスダイアグラムの詳細構造を用いた線形符号の再帰的最ゆう復号アルゴリズムについての平均計算複雑度の評価
- 逐次復号法の繰り返し回数を減少させるための条件
- 新しい逐次軟判定復号法
- セクショントレリスダイアグラムを用いた線形符号の最尤復号の複雑度について
- 二元線形ブロック符号に対する再帰的Log-MAPアルゴリズム
- 大学における講義評価のための匿名アンケートプロトコルとその試作(セキュリティと社会)
- ギャップの大きなLDPC符号に対する Richardson 符号化法の効率改善
- SFA-LDPC符号の最小重み符号語数について(LDPC符号セッション(重み分布),LDPC符号,及び一般)
- あるパラメータを有するSimple Full-length Array LDPC符号の最小重みについて(情報通信基礎サブソサイエティ合同研究会)
- あるパラメータを有するSimple Full-length Array LDPC符号の最小重みについて(情報通信基礎サブソサイエティ合同研究会)
- あるパラメータを有するSimple Full-length Array LDPC符号の最小重みについて(情報通信基礎サブソサイエティ合同研究会)
- 有界経路重なり項書換え系の停止性問題について (計算理論とアルゴリズムの新展開)
- 項宣言および順序ノート付き単一化問題の木オートマトンを用いた解法
- 複数の大規模グループに同時参加するセンサノード向けグループ鍵管理方式
- 符号の剰余類分割を利用した最尤復号特性評価法について
- 符号の剰余類分割を利用した最尤復号特性評価法について
- 符号の剰余類分割を利用した最尤復号特性評価法について
- 符号の剰余類分割を利用した最尤復号特性評価法について
- センサネットワークにおける有限幾何を利用した鍵事前格納方式
- セクショントレリス線図を用いたMAP復号アルゴリズム
- Index-Less型フラッシュ符号におけるオーバヘッドの小さなブロックサイズ削減手法
- 代入制約付き構文的単一化問題の計算量
- 代入に制約がある場合の構文的単一化可能性判定問題
- 線形符号の局所的な検査行列を利用した最尤復号アルゴリズム
- 2元線形ブロック符号の再帰的軟判定復号法について
- 線形符号の局所的な検査行列を利用した最尤復号アルゴリズム
- 2元線形ブロック符号の再帰的軟判定復号法について
- 線形符号の局所的な検査行列を利用した最尤復号アルゴリズム
- 2元線形ブロック符号の再帰的軟判定復号法について
- 三角分解を用いたLDPC符号化法の計算量について
- 行列の三角分解を利用したLDPC符号化アルゴリズム
- 頑強性の定式化と識別不可能性との含意関係について
- 再帰的最尤復号法における送信系列の統計的振舞いについて
- D-19-2 センサネットワークにおける安全で効率的な受信確認方式(D-19.情報通信システムセキュリティ,一般セッション)
- 非一様な書き換えに対するIndex-Less型フラッシュ符号の性能評価
- 複数の大規模グループに同時参加するセンサノード向けグループ鍵管理方式 (特集 マルチメディア、分散、協調とモバイルシステム)
- 代入に制限がある場合の項書き換え系の単一化可能性問題について