|Title||Decidability Under the Well-Founded Semantics|
|Publication Type||Conference Paper|
|Year of Publication||2007|
|Authors||Pascal Hitzler, Natalia Cherchago, Steffen Holldobler|
|Conference Name||First International Conference on Web Reasoning and Rule Systems, RR2007|
|Conference Location||Innsbruck, Austria|
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 . 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.