二分決定グラフ上での知識表現および正/ホーン関数の認識問題

スポンサーリンク

概要

• 論文の詳細を見る

• 二分決定グラフを知識ベースの処理手段として利用することを提案し、この手法の有効性を示す。すなわち、二分決定グラフによる表現は、記憶容量の観点において既存のCNF論理式による方法、モデル(充足割当)による方法よりも指数的に小さくなる場合があることを示す。また、二分決定グラフの認識問題について考察を行い、与えられた二分決定グラフの表す関数が正関数か、ホーン関数かのそれぞれを多項式時間で判定するアルゴリズムを提案する。

• 社団法人電子情報通信学会の論文
• 1999-03-24

著者

• 堀山 貴史

  埼玉大学大学院理工学研究科

• 堀山 貴史

  京都大学大学院情報学研究科

• 堀山 貴史

  埼玉大学理工学研究科

• 堀山 貴史

  奈良先端科学技術大学院大学

• 堀山 貴史

  京都大学大学院 工学研究科

• 茨木 俊秀

  京都大学大学院情報学研究科

• 茨木 俊秀

  京都大学情報学研究科

• 茨木 俊秀

  京都大学大学院工学研究科数理工学専攻

関連論文

• 最長路問題とJR大都市近郊区間大回りへの応用
• ポリオミノのp4タイリングの列挙
• A Set Covering Approach for the Pickup and Delivery Problem with Additional Constraints (Numerical Optimization methods, theory and applications)
• 多制約配送計画問題に対する集合被覆アプローチ
• 2-A-3 MAX-2-SATに対する分枝限定法の改良(離散最適化(3))
• MAX-2-SATに対する分枝限定法(組合せ最適化(4))
• 勤務スケジューリング問題に対する局所探索法(医療・福祉・スケジューリング(2))
• 凸型時間ずれコストをもつ資源制約スケジューリング問題(統合オペレーション)
• TD-1-5 汎用スケジューラー : RCPSPによるアプローチ
• 分離可能凸型コスト関数をもつプロジェクトスケジューリング問題(スケジューリング)
• 汎用スケジューラー : RCPSPによるアプローチ (アルゴリズム工学)
• 資源制約付きスケジューリング問題の定式化と近似解法 (新しいパラダイムとしてのアルゴリズム工学)
• 汎用アルゴリズムとしてのCSP(制約充足問題)に対するタブー探索アプローチ(離散数理と連続数理における最適化理論)
• DS-1-14 飛び道具を考慮した逆算法に基づく詰将棋列挙技術(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
• Automatic clock gating generation through power-optimal control signal selection (VLSI設計技術)
• 「問題解決エンジン」への道
• 工学としてのアルゴリズム
• 集合被覆問題に対する3反転近傍を明いた局所探索法
• D-1-5 Horn CNF とその二分決定グラフ表現間の変換の計算複雑さ
• Deduction and Abduction with Ordered Binary Decision Diagrams (Foundations of Computer Science)
• Ordered Binary Decision Diagrams Representing Knowledge-Bases (Models of Computation and Algorithms)
• 二分決定グラフ上での知識表現および正/ホーン関数の認識問題
• 数理計画 : 問題解決への広き門(ユーザのための数理計画入門)
• 複数の二分決定グラフを用いたNP完全な組合せ問題の解法
• 正4面体と他の正多面体との共通の辺展開図に関する研究
• 自動クロックゲーティング生成における電力最適化制御信号選択手法
• 演繹データベースにおける直積問題クラスとそのアルゴリズム
• 秘密分散を用いた安全なVickreyオークション
• MAX-2-SATに対する分枝限定法
• ルール生成に必要なデータ量に関するランダム性に基づいた解析
• 1-D-1 ルール生成に必要なデータ量に関するランダム性に基づいた解析(マーケティング(1))
• オプションプライシングと凸計画問題の関係について(金融工学(3))
• 長方形詰込み問題に対する可変近傍探索法(組合せ最適化(4))
• 移動時間コスト関数を考慮した時間枠つき配送計画問題に対する局所探索法 (数理最適化から見た「凸性の深み,非凸性の魅惑」)
• Local Search Algorithms for the Two-Dimensional Cutting Stock Problem with a Given Number of Different Patterns (Captivation of Convexity : Fascination of Nonconvexity)
• 移動時間コスト関数を考慮した時間枠つき配送計画問題に対する局所探索法(組合せ(1))
• 段取り替え制約付きカッティングストック問題に対する列生成法を用いた局所探索法の提案(組合せ(1))
• 逆探索によるp4タイリングの列挙 (理論計算機科学の深化と応用)
• 論理関数の畳み込み機構を導入した省面積FPGAの実現と評価
• 8C45 ことばによる手話単語の記述と三次元表現
• 配置コストをもつ長方形詰込み問題に対する局所探索法の高速化 (最適化の数理とアルゴリズム)
• 配置コストをもつ長方形詰込み問題に対する局所探索法の高速化
• 配置コストをもつ長方形詰込み問題に対する局所探索法の高速化(組合せ最適化(2))
• 配置コストをもつ長方形詰込み問題に対する局所探索法について(統合オペレーション(4))
• TD-1-6 組合せ最適化問題に対する局所探索アルゴリズムの開発について
• 配置コストをもつ二次元配置問題に対する局所探索について(組合せ最適化)
• 非線形方程式と整数解の探索に基づく高位合成向けビット長最適化(検証・理論, 組込技術とネットワークに関するワークショップ)
• 非線形方程式と整数解の探索に基づく高位合成向けビット長最適化
• 非線形方程式と整数解の探索に基づく高位合成向けビット長最適化(検証・理論, 組込技術とネットワークに関するワークショップ)
• 非線形方程式と整数解の探索に基づく高位合成向けビット長最適化
• ATMスイッチにおけるタイマ・チャネル割付けについて
• 藤重, 岩田先生Fulkerson賞受賞のニュース(情報の窓)
• Support Vector Machineにおけるルールの利用(線形計画)
• カッティングストック問題に対する線形計画法に基づく局所探索法の提案 (最適化の数理とアルゴリズム)
• 閾グラフの最小辺ランキング全域木について
• 「高度応用のための情報ベースモデルとその実現技術」を目指して (メディア統合および環境統合のための高機能データベースシステム、および一般)
• 総論 (特集 アルゴリズムの新展開--理論から工学へ)
• アルゴリズムの道具箱・基礎編(最終回)巡回セールスマン問題
• C言語を用いた音声認識・学習LSIの設計と実現について
• C言語を用いた音声認識・学習LSIの設計と実現について
• C言語を用いた音声認識・学習LSIの設計と実現について
• A-3-13 学習回路インターフェースを持ち不特定話者に対応できる音声認識回路
• マルチステージクロックゲーテイングにおけるクロック制御回路の共有について(低電力設計,デザインガイア2010-VLSI設計の新しい大地-)
• マルチステージクロックゲーティングにおけるクロック制御回路の共有について(低電力設計,デザインガイア2010-VLSI設計の新しい大地-)
• 1-D-5 最長路問題と最大経路差問題 : その解法とJR大都市近郊区間大回りへの応用(離散・組合せ最適化(2))
• データ分類におけるノイズ量の評価について(数理計画(1))
• New Graph Calculi for Planar Non-3-Colorable Graphs
• オンライン問題の競合比解析の自動化について
• 平面グラフにおけるHajos Calculusの複雑さについて
• 二段組合せ回路の最大動作率について(計算理論とアルゴリズムの新展開)
• 入札額の範囲が制限された正直なオークション
• Hajos Calculus on Planar Graphs (Theoretical Computer Science and its Applications)
• 論理式の解密度の濃縮
• FOCS 2008報告
• 上位からの時差入力下での最適並列加算器
• 除算を表現する二分決定グラフの指数下界
• 抽象解釈手法に基づく変数の相互関係解析とそのデータパス最適化への応用(システム設計及び一般)
• 抽象解釈手法に基づく変数の相互関係解析とそのデータパス最適化への応用(システム設計および一般)
• 論理関数の畳み込み機構を導入した省面積FPGAの実現と評価
• 論理関数の畳み込み機構を導入した省面積FPGAの実現と評価(FPGAとその応用及び一般)
• A-3-25 論理関数の重ね合わせに基づく加減算向きLUT
• A-3-4 リング発振器を用いたオンチップ高速シリアル通信方式
• A-3-11 冗長2進CORDIC演算器を有する16ビットパイプラインプロセッサ
• Fine-Grained Power Gating Based on the Controlling Value of Logic Elements
• Fine-grained power gating based on the controlling value of logic gates (VLSI設計技術)
• Fine-grained power gating based on the controlling value of logic gates (システムLSI設計技術)
• Bit-Length Optimization Method for High-Level Synthesis Based on Non-linear Programming Technique(System Level Design,VLSI Design and CAD Algorithms)
• DS-1-7 いかなる辺展開でも正多面体は重ならない(DS-1.COMP学生シンポジウム,シンポジウムセッション)
• いかなる辺展開でも正多面体は重なりを持たない (計算機科学とアルゴリズムの数理的基礎とその応用)
• 正4面体と正6面体との共通の展開図の構成に関する研究
• 正多面体の展開図における最小/最大の直径、幅および包囲長方形について
• いかなる辺展開でも正多面体は重なりを持たない
• 正多面体の展開図における最小/最大の直径、幅および包囲長方形について
• 任意の凸多面体は重なりのない展開図に展開できるだろうか?
• 2-K-10 p6タイリング可能なポリアモンドの生成(ワークショップ「娯楽のOR-エンターテイメントの数理」)
• On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)
• アスペクト比を固定した最小の周囲長方形について (アルゴリズムと計算理論の新展開)
• 多面体の非同型な展開図の個数について
• 基単調図形に分割可能な最大重み領域を得る基線の配置問題
• トロミノ詰込問題の計算複雑さについて

もっと見る 閉じる

スポンサーリンク