کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10320264 | 658375 | 2010 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Outlier detection for simple default theories
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Outlier detection for simple default theories Outlier detection for simple default theories](/preview/png/10320264.png)
چکیده انگلیسی
It was noted recently that the framework of default logics can be exploited for detecting outliers. Outliers are observations expressed by sets of literals that feature unexpected properties. These observations are not explicitly provided in input (as it happens with abduction) but, rather, they are hidden in the given knowledge base. Unfortunately, in the two related formalisms for specifying defaults - Reiter's default logic and extended disjunctive logic programs - the most general outlier detection problems turn out to lie at the third level of the polynomial hierarchy. In this note, we analyze the complexity of outlier detection for two very simple classes of default theories, namely NU and DNU, for which the entailment problem is solvable in polynomial time. We show that, for these classes, checking for the existence of an outlier is anyway intractable. This result contributes to further showing the inherent intractability of outlier detection in default reasoning.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 174, Issue 15, October 2010, Pages 1247-1253
Journal: Artificial Intelligence - Volume 174, Issue 15, October 2010, Pages 1247-1253
نویسندگان
Fabrizio Angiulli, Rachel Ben-Eliyahu-Zohary, Luigi Palopoli,