Deductive Inference for the Interiors and Exteriors of Horn Theories
Kaz Makino
abstract:
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
\cite{interior} 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.
This is a joint work with Hirotaka Ono (