部分定義ブール関数のダブルホーン拡張および限定ホーン拡張

摘要

本稿では，与えられた部分定義ブール関数(pdBf) についてダブルホーン，限定ホーンによる拡張を見つける問題を考える。 このような問題を解くことによって，生成規則知識ベースを単純化することができる。 また，一般に命題推論の計算動作の改良にもつながる。このとき，単純化の中でも(i) 知識ベースサイズの最小化と(ii) 推論の計算が効率的に行われるように生成規則の表現を変えることが重要である。本稿では(i) ，(ii) を達成するダブルホーン拡張と限定ホーン拡張について，その充足解の数において極小な拡張を多項式時間に求める方法を議論する。 一方，それぞれの最小の拡張を求める問題がNP困難であることを示す。