  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 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.
