部分定義論理関数のホーン拡張について
スポンサーリンク
概要
- 論文の詳細を見る
本論文では, 部分定義論理関数(T,F)に対するホーン拡張 f:{0,1}^n⟼{0,1}について考察する. ただし, T⊆{0,1}^nは正例の集合, F⊆{0,1}^nは負例の集合を表すものとする. (T,F)が与えられたとき, ホーン拡張が存在するかどうか多項式時間決定可能であることが知られているが, 複数のホーン拡張が存在するので, 極大あるいは, 極小の真ベクトル集合T(f)をもつ拡張 f について考察する. 任意の(T,F)に対して, 唯一の極大(すなわち,最大)ホーン拡張が存在するが, 一般に, たくさんの極小ホーン拡張が存在する. 我々は, まず, 極大ホーン拡張に対して, たとえそのDNF表現が長くなるときでも, 多項式時間帰属性神託が構成可能であるを示す. さらに, 与えられたホーンDNFが極小ホーン拡張を示すかどうかの決定, 極小ホーン拡張のホーンDNF表現の構成, また, (T,F)が唯一の極小ホーン拡張をもつかどうかの決定がすべて多項式時間可能であることを示す. 最後に, 最小の|T(f)|をもつホーン拡張, および, リテラル数が最小のDNF表現をもつホーン拡張を求める問題がNP-困難であるを示す.
- 一般社団法人情報処理学会の論文
- 1996-03-15
著者
関連論文
- 衝突回避減速度に基づく前方障害物衝突防止支援システム
- 衝突回避減速度を用いたリスク評価指標の提案
- 前方障害物の視認性に基づく環境適合型警報タイミングの効果評価
- ドライビングシミュレータを用いた夜間運転支援システムの効果評価
- 双対制限された列挙問題 : 離散分布に対する交差不等式とその応用
- ラミナー被覆制約を持つ単調凹関数最小化問題
- 木構造の動的ネットワーク上の施設配置問題に対するO(nlog^2n)時間アルゴリズム
- An O(nlog^2n)Algorithm for the Optimal Sink Lacation Problem on Dynamic Tree Networks
- 動的交通流配分のネットワーク・モデル
- スケジューリングの理論
- A-17-5 ブースティングを用いた遠赤外画像における歩行者検出(A-17.ITS,一般講演)
- 遠赤外線カメラを用いた歩行者検知システムの開発
- 自動車 遠赤外線カメラを用いた夜間歩行者検知システムの開発
- 部分定義論理関数のホーン拡張について
- 給油施設操業スケジューリング
- 閾グラフの最小辺ランキング全域木について
- 最小辺ランキング全域木問題について
- On Minimum Edge Ranking Spanning Trees
- 劣モジュラ, 正モジュラ集合関数の多重グラフによる増大法
- 初等的フローゲームの凸性について(計算量理論とアルゴリズム論文小特集)
- フローゲームの凸性について(ゲーム理論(2))
- 辺連結度,点連結度を同時に最適増大させる問題
- 機械式立体駐車場入出庫スケジューリング
- 機械式立体駐車場出庫スケジューリング
- 無向ネットワークにおける流量要求を満たす施設配置問題
- ネットワーク上の被覆型施設配置問題(グラフ・ネットワーク(3))
- Vehicle Scheduling on a Tree to Minimize Maximum Lateness(スケジューリング(2))
- 正則コテリの効率的な列挙について
- 正則2部グラフに対する単純なマッチングアルゴリズム
- 正決定木によるデータ解析(組合せ最適化(1))
- 部分定義論理関数の正論理関数とHorn関数における関数分解について
- 正理論関数の部分データに基づく正決定木の構成について(組み合わせ最適化(3))
- メタ戦略とラグランジュ緩和(「スケジューリング技術の新たな展開特集号」)
- 不完全データの論理的解析
- 不完全例題に対するプール的解析
- Extensions of Partially Defined Boolean Functions with Missing Data
- Error-Free and Best-Fit Extensions of Partially Defined Boolean Functions
- 双対制限されたハイパーグラフ:部分横断と多重横断の列挙について
- 単調線形システムにおけるすべての極小な整数解について
- ハイパーグラフの重み付き横断
- オイラー有向グラフにおける2本の辺素なパスの存在判定
- 複基多面体:台の大きさが2以下の辺ベクトルを有する多面体の構造
- フロー制約を持つソース配置問題に対する近似アルゴリズム
- 木構造動的ネットワークにおける複数個の施設配置問題(組合せ最適化(5))
- 木構造動的ネットワークにおける複数の施設への避難誘導問題(数理計画関連・数理モデル)
- 木構造の動的ネットワークにおける施設配置問題
- 木構造の動的ネットワークにおける施設配置問題(グラフ・ネットワーク(2))
- 単調双対化問題とハイパーグラフ横断列挙問題に対する新しい結果について
- ホーン理論とq-ホーン理論の極小関数従属性の推定について
- ハイパーグラフの重み付き横断
- 最適化アルゴリズムの最近の動き
- 数値データの論理的分析(組合せ最適化(3))
- 無向グラフにおけるk-辺分割問題の一般化について
- 無向ネットワーク中のソース配置問題の強NP困難性とその近似アルゴリズム(組合せ最適化(5))
- LA-002 無向ネットワーク中のソース配置問題に対する近似アルゴリズム(A. モデル・アルゴリズム・プログラミング)
- ラミナー被覆制約を持つ単調凹関数最小化問題(グラフ・ネットワーク)
- 論理的データ解析における階層的分解構造について
- O(log n)項単調論理和標準形の効率的な双対化について
- 部分定義ブール関数のダブルホーン拡張および限定ホーン拡張
- ホーン理論と推論問題(理論計算機科学の最新動向)
- ハイブリッド画像センサの開発
- Double Horn Functions
- Double Horn Functions
- データの論理的解析とブール関数
- データの論理的解析とブール関数
- 部分定義論理関数の内核関数と外核関数
- 2-単調正論理関数の同定問題に対する単純な高速アルゴリズム
- Interior and Exterior Functions of Positive Boolean Functions
- 論理関数の内包関数と外包関数について
- 正論理関数の最大潜伏度の同定(計算量理論)
- 不完全に定義された正論理関数の最大潜伏度について
- 正論理関数の最大潜伏度について(計算機構とアルゴリズム)
- 2-F-4 オンラインナップサック問題に対する乱択アルゴリズム(離散最適化(5))