Decidability Under the Well-Founded Semantics

TitleDecidability Under the Well-Founded Semantics
Publication TypeConference Paper
Year of Publication2007
AuthorsPascal Hitzler, Natalia Cherchago, Steffen Holldobler
Conference NameFirst International Conference on Web Reasoning and Rule Systems, RR2007
Conference LocationInnsbruck, Austria
Abstract

The well-founded semantics (WFS) for logic programs is one of the few major paradigms for closed-world reasoning. With the advent of the Semantic Web, it is being used as part of rule systems for ontology reasoning, and also investigated as to its usefulness as a semantics for hybrid systems featuring combined open- and closed-world reasoning. Even in its most basic form, however, the WFS is undecidable. In fact, it is not even semi-decidable, which means that it is a theoretical impossibility that sound and complete reasoners for the WFS exist. Surprisingly, however, this matter has received next to no attention in research, although it has already been shown in 1995 by John Schlipf [1]. In this paper, we present several conditions under which query-answering under the well-founded semantics is decidable or semi-decidable. To the best of our knowledge, these are the very first results on such conditions.

Full Text

Natalia Cherchago, Pascal Hitzler, Steffen Holldobler, 'Decidability Under the Well-Founded Semantics,' First International Conference on Web Reasoning and Rule Systems, RR2007, Innsbruck, Austria, June 2007, pp. 269-278.
pages: 269-278
year: 2007
venue name: First International Conference on Web Reasoning and Rule Systems, RR2007

Related Files: