Deductive Inference for the Interiors and Exteriors of Horn Theories

機関リポジトリ (HANDLE) オープンアクセス

説明

In this paper, we investigate the deductive inference for the interiors and exteriors of Horn knowledge bases, where the interiors and exteriors were introduced by Makino and Ibaraki [11] to study stability properties of knowledge bases. We present a linear time algorithm for the deduction for the interiors and show that it is co-NP-complete for the deduction for the exteriors. Under model-based representation, we show that the deduction problem for interiors is NP-complete while the one for exteriors is co-NP-complete. As for Horn envelopes of the exteriors, we show that it is linearly solvable under model-based representation, while it is co-NP-complete under formula-based representation. We also discuss the polynomially solvable cases for all the intractable problems.

収録刊行物

詳細情報 詳細情報について

  • CRID
    1050861482659152896
  • NII論文ID
    120006654469
  • HANDLE
    2324/14863
  • 本文言語コード
    en
  • 資料種別
    conference paper
  • データソース種別
    • IRDB
    • CiNii Articles

問題の指摘

ページトップへ