- 【Updated on May 12, 2025】 Integration of CiNii Dissertations and CiNii Books into CiNii Research
- Trial version of CiNii Research Knowledge Graph Search feature is available on CiNii Labs
- Suspension and deletion of data provided by Nikkei BP
- Regarding the recording of “Research Data” and “Evidence Data”
Deductive Inference for the Interiors and Exteriors of Horn Theories
-
- Makino, Kazuhisa
- Department of Mathematical Informatics, University of Tokyo
-
- Ono, Hirotaka
- Department of Computer Science and Communication Engineering, Kyushu University
Description
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.
Journal
-
- Lecture Notes in Computer Science
-
Lecture Notes in Computer Science 5369 390-401, 2008-12-11
Springer
- Tweet
Details 詳細情報について
-
- CRID
- 1050861482659152896
-
- NII Article ID
- 120006654469
-
- HANDLE
- 2324/14863
-
- Text Lang
- en
-
- Article Type
- conference paper
-
- Data Source
-
- IRDB
- CiNii Articles
