کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10320283 | 658402 | 2005 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An incremental algorithm for generating all minimal models
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The task of generating minimal models of a knowledge base is at the computational heart of diagnosis systems like truth maintenance systems, and of nonmonotonic systems like autoepistemic logic, default logic, and disjunctive logic programs. Unfortunately, it is NP-hard. In this paper we present a hierarchy of classes of knowledge bases, Ψ1,Ψ2,â¦â, with the following properties: first, Ψ1 is the class of all Horn knowledge bases; second, if a knowledge base T is in Ψk, then T has at most k minimal models, and all of them may be found in time O(lk2), where l is the length of the knowledge base; third, for an arbitrary knowledge base T, we can find the minimum k such that T belongs to Ψk in time polynomial in the size of T; and, last, where K is the class of all knowledge bases, it is the case that âi=1âΨi=K, that is, every knowledge base belongs to some class in the hierarchy. The algorithm is incremental, that is, it is capable of generating one model at a time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 169, Issue 1, November 2005, Pages 1-22
Journal: Artificial Intelligence - Volume 169, Issue 1, November 2005, Pages 1-22
نویسندگان
Rachel Ben-Eliyahu - Zohary,