Equality-friendly well-founded semantics and applications to description logics

Clemens Kupke, Georg Gottlob, Thomas Lukasiewicz, Andre Hernich

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

55 Downloads (Pure)


We tackle the problem of defining a well-founded semantics (WFS)
for Datalog rules with existentially quantified variables in their heads and nega-
tions in their bodies. In particular, we provide a WFS for the recent Datalog±
family of ontology languages, which covers several important description logics
(DLs). To do so, we generalize Datalog± by non-stratified nonmonotonic nega-
tion in rule bodies, and we define a WFS for this generalization via guarded fixed
point logic. We refer to this approach as equality-friendly WFS, since it has the
advantage that it does not make the unique name assumption (UNA); this brings
it close to OWL and its profiles as well as typical DLs, which also do not make
the UNA. We prove that for guarded Datalog± with negation under the equality-
friendly WFS, conjunctive query answering is decidable, and we provide precise
complexity results for this problem. From these results, we obtain precise defi-
nitions of the standard WFS extensions of EL and of members of the DL-Lite
family, as well as corresponding complexity results for query answering.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence
Number of pages8
Publication statusPublished - 2012
EventAAAI-2012: Twenty-Sixth Conference on Artificial Inetelligence - Toronto, Canada
Duration: 24 Jul 2012 → …


ConferenceAAAI-2012: Twenty-Sixth Conference on Artificial Inetelligence
Period24/07/12 → …


  • datalog
  • artificial intelligence


Dive into the research topics of 'Equality-friendly well-founded semantics and applications to description logics'. Together they form a unique fingerprint.

Cite this