Deductive inference for the interiors and exteriors of horn theories
Kazuhisa Makino, Hirotaka Ono · ACM Transactions on Computational Logic · 2012
In this article, we investigate deductive inference for interiors and exteriors of Horn knowledge bases, where interiors and exteriors were introduced by Makino and Ibaraki [1996] to study stability properties of knowledge bases. We present a linear time algorithm for deduction for interiors and show that deduction is coNP-complete for exteriors. Under model-based representation, we show that the deduction problem for interiors is NP-complete while the one for exteriors is coNP-complete. As for Horn envelopes of exteriors, we show that it is linearly solvable under model-based representation, while it is coNP-complete under formula-based representation. We also discuss polynomially solvable cases for all the intractable problems.