特許
J-GLOBAL ID：200903033602452418
充足可能性判定問題の高速判定装置
発明者：
出願人/特許権者：
代理人 (1件)：
岡田 守弘
公報種別：公開公報
出願番号（国際出願番号）：特願平6-033379
公開番号（公開出願番号）：特開平7-244654
出願日： 1994年03月03日
公開日（公表日）： 1995年09月19日
要約：
【要約】【目的】 本発明は、充足可能性判定問題を高速に判定する高速判定装置に関し、いろいろな性質を有する充足可能性判定問題を1CNF、2CNF、およびnCNF(n≧3)の3種類に分類して効率的かつ高速に解を求めることを目的とする。【構成】 与えられた複数の和項の論理積で表される充足可能性判定問題を解析して和項内の変数が1つの1CNF、和項内の変数が2つの2CNF、および和項内の変数が3よりも大きいnCNFに分類するCNF解析部2と、分類された1CNFの変数の値を決定する1CNF処理部3と、分類された2CNFの変数の値を決定する2CNF処理部4と、分類されたnCNFの変数の値を決定するnCNF処理部5とを備え、これら1CNF処理部3、2CNF処理部4およびnCNF処理部5で充足する変数の値がそれぞれ見つかったときに解有りと判定するように構成する。
請求項（抜粋）：
充足可能性判定問題を高速に判定する高速判定装置において、与えられた、複数の和項の論理積で表される充足可能性判定問題を解析して和項内の変数が1つの1CNF、和項内の変数が2つの2CNF、および和項内の変数が3よりも大きいnCNFに分類するCNF解析部(2)と、分類された1CNFの変数の値を決定する1CNF処理部(3)と、分類された2CNFの変数の値を決定する2CNF処理部(4)と、分類されたnCNFの変数の値を決定するnCNF処理部(5)とを備え、これら1CNF処理部(3)、2CNF処理部(4)およびnCNF処理部(5)で充足する変数の値がそれぞれ見つかったときに解有りと判定することを特徴とする充足可能性判定問題の高速判定装置。
IPC (2件)：
FI (2件)：
G06F 15/31 Z
, G06F 15/20 Z
