Tractable Strong Outlier Identification

Details Tractable Strong Outlier Identification Tractable Strong Outlier Identification

2011-09-21

arxiv.org/abs/1109.4623v1

Computer Science

Artificial Intelligence

Scientific paper

In knowledge bases expressed in default logic, outliers are sets of literals, or observations, that feature unexpected properties. This paper introduces the notion of strong outliers and studies the complexity problems related to outlier recognition in the fragment of acyclic normal unary theories and the related one of mixed unary theories. We show that recognizing strong outliers in acyclic normal unary theories can be done in polynomial time. Moreover, we show that this result is sharp, since switching to either general outliers, cyclic theories or acyclic mixed unary theories makes the problem intractable. This is the only fragment of default theories known so far for which the general outlier recognition problem is tractable. Based on these results, we have designed a polynomial time algorithm for enumerating all strong outliers of bounded size in an acyclic normal unary default theory. These tractability results rely on the Incremental Lemma, an interesting result on its own, that provides conditions under which a mixed unary default theory displays a monotonic reasoning behavior.

Affiliated with

Also associated with

No associations

Rating

Tractable Strong Outlier Identification 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 Tractable Strong Outlier Identification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tractable Strong Outlier Identification will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-258199