On the completeness of SLDNF-resolution.
Item
-
Title
-
On the completeness of SLDNF-resolution.
-
Identifier
-
AAI9029978
-
identifier
-
9029978
-
Creator
-
Shen, Zhizhang.
-
Contributor
-
Adviser: Howard C. Wasserman
-
Date
-
1990
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science | Mathematics
-
Abstract
-
By the completeness of logic programming, we mean that all inferences supported by the declarative semantics are also supported by the procedural semantics. In the context of this dissertation, the completed program semantics is the declarative semantics and SLDNF-resolution is the procedural correspondent.;In this dissertation, after reviewing the basic syntactical and semantical issues for first order logic, and in particular, for logic programs, we carry out a systematic study of completeness for logic programming: we present some causes for incompleteness of SLDNF-resolution with respect to the completed program semantics; we then review a series of completeness results for several related classes of logic programs and present an extension of a known completeness result.;Moreover, we put forward a new approach towards obtaining completeness results: we begin with an interesting example of incompleteness, and go on to develop the idea of the coincidence of two semantics, one defined in terms of the so-called declaratively-relevant part of a logic program with respect to a goal, and the other defined in terms of the so-called procedurally-relevant part. Based on the close relationship between the semantic coincidence and completeness, we provide a new characterization of the completeness of SLDNF-resolution with respect to the completed program semantics. Finally, we give an effectively decidable condition equivalent to completeness, under a set of reasonable restrictions on the programs and goals. As the condition is in no means necessary, it is expected that yet weaker conditions may be obtained following this approach.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
