Deductive Inference for the Interiors and Exteriors of Horn Theories

Details Deductive Inference for the Interiors and Exteriors of Horn Theories Deductive Inference for the Interiors and Exteriors of Horn Theories

2009-03-03

arxiv.org/abs/0903.0422v1

Computer Science

Artificial Intelligence

20 pages, 1 figure, An extended abstract of this article was presented in Proceedings of Algorithms and Computation, 19th Inte

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Deductive Inference for the Interiors and Exteriors of Horn Theories does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Deductive Inference for the Interiors and Exteriors of Horn Theories, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deductive Inference for the Interiors and Exteriors of Horn Theories will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-652424