節集合の対称性を利用したSATCHMOによる充足可能性判定
スポンサーリンク
概要
- 論文の詳細を見る
ボトムアップ型の定理証明器としてこれまでにDavis-Putnam手続きやSATCHMOなどが考案されている.しかし, 命題論理の充足可能性判定問題はNP完全であるため, いかに高性能な定理証明器を用いても問題のサイズが大きくなれば証明時間が爆発的に増大してしまう.大きな定理証明問題をこれ以上速く解くには, 定理証明問題の持つ特性を利用しなくてはならない.そこで本研究では, ボトムアップ定理証明器SATCHMOヘシンメトリ(対称性)の概念を導入する.また、単位リテラル規則・純リテラル規則を導入して命題節集合の縮小化を行う.さらに, 実験により充足可能性の判定を効率良くできることを確認する.
- 一般社団法人情報処理学会の論文
- 1998-07-15
著者
関連論文
- 競合状況における投機的計算の導入に関する考察(自動推論 : 演繹, 帰納, モデル検査/生成, 仮説推論アブダクション, 論理プログラム, プランニング, 時相論理, etc.)
- SATソルバの並列実行に関する一考察(「自動推論:帰納,演繹,モデル検査/生成,学習,発見,仮説推論,論理プログラム,プランニングetc.」及び一般)(自動推論)
- 優先的解集合の論理プログラミングによる計算(「自動推論:帰納,演繹,モデル検査/生成,学習,発見,仮説推論,論理プログラム,プランニングetc.」及び一般)(自動推論)
- [招待論文]結論発見手続きとその応用(「自動推論:帰納,演繹,モデル検査/生成,学習,発見,仮説推論,論理プログラム,プランニングetc.」及び一般)(自動推論)
- ペナルティ関数法によるSAWフィルタのロバスト最適設計
- ダイアグラムに基づく法的論争支援システム
- アフォーダンス理論による人工技能への接近 : 記憶と身体性
- 今西進化論に基づく遺伝アルゴリズムによる多様なパレート最適解の抽出法 - 多目的資源分割問題を実例として -
- モデル消去法に基づくSOL導出の実現
- 遺伝的アルゴリズムとアフォーダンスを用いた知能ロボットの創発
- 距離に基づく遺伝アルゴリズムの構築法 -表現型の距離と調和交叉法-
- 巡回セールスマン問題に対する遺伝的アルゴリズムの構成法 : 表現型の距離と調和交叉法
- CF帰納法における一般化に関する考察
- エージェント間通信におけるアブダクションによる投機的計算(マルチエージェント)
- 遺伝アルゴリズムを枠組としたメタ戦略の構築法-グラフ彩色問題を実例として-
- デフォルト規則を含む拡張論理プログラムの学習
- 節集合の対称性を利用したSATCHMOによる充足可能性判定
- タブローに基づく論理的帰結発見手続きSOL
- SATソルバと後ろ向き推論によるアクション言語Αの実装
- アクション言語のためのボトムアップ処理系
- ノンホーンマジックセット法と関連性テストとの等価性
- 補題の利用による効率的なSOL導出の実現
- 有限オートマトンに基づく非決定性アクション言語
- アクション言語Aにおける行動規則の学習
- 拡張論理プログラム学習へのトップダウン手続きの組込み
- プランニンググラフとSATプランニング(「プランニング技術の進展と新たな応用展開」)
- Java言語によるアクション言語処理系の実装