Decidability Under the Well-Founded Semantics

Document Type

Conference Proceeding

Publication Date

6-2007

Find this in a Library

Catalog Record

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.

Comments

Presented at the First International Conference on Web Reasoning and Rule Systems, Innsbruck, Austria, June 7-8, 2007.

DOI

10.1007/978-3-540-72982-2_21

Link to Full Text

Catalog Record

Share

COinS