Reasoning with the Description Logic DLRO ¡fg using Bound Guarded Programs
Stijn Heymans, Davy Van Nieuwenborgh, Dieter Fensel, Dirk Vermeir · 2006
Open answer set programming combines the strengths of logic pro- gramming (a rule-based presentation and a nonmonotonic seman- tics) and description logics (open domains). Reasoning under an open answer set semantics is undecidable in general, but decidabil- ity can be obtained for particular classes of logic programs, e.g., for bound guarded programs. In this paper, we show how bound guarded programs are expressive enough to simulate satisability checking in a DL with n-ary roles and nominals, yielding EXP- TIME-completeness for both the DL reasoning and the reasoning with bound guarded programs under the open answer set seman- tics. We establish decidability of three query problems (query con- tainment, consistency, and disjointness) for guarded queries by a reduction to bound guarded programs, resulting in an EXPTIME up- per bound.