کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
434528 689750 2013 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Generalized satisfiability for the description logic ALC
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Generalized satisfiability for the description logic ALC
چکیده انگلیسی

The standard reasoning problem, concept satisfiability, in the basic description logic ALC  is PSpace-complete, and it is ExpTime-complete in the presence of general concept inclusions. Several fragments of ALC, notably logics in the FL, EL, and DL-Lite families, have an easier satisfiability problem; for some of these logics, satisfiability can be decided in polynomial time. We classify the complexity of the standard variants of the satisfiability problem for all possible Boolean and quantifier fragments of ALC  with and without general concept inclusions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 505, 23 September 2013, Pages 55-73