Kaz Makino

University of Tokyo

Title: Deductive Inference for the Interiors and Exteriors of Horn Theories

In this paper, we investigate the deductive inference for the interiors

and exteriors of Horn 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 (Kyusyu Univ.)