A study of the well-founded and stable logic programming semantics

Logic programming semantics produce the sets of all logically deducible propositions from a set of logic formulas called a logic program. The stable and the well-founded semantics give meaning to logic programs containing rules with negative hypotheses such as "the specimen is not a mammal". Computation of these semantics in the propositional case is (worst case) exponential and quadratic, respectively.; This doctoral dissertation presents a multi-faceted pursuit involving these semantics. These facets include results from complexity theory, graph theory, and machine learning. Some of the important results are: (1) the computation of the stable semantics in linear time for five newly discovered classes of normal logic programs, (2) the computation of the well-founded semantics in linear time for uni-rule programs, another newly discovered class of logic programs, (3) the NP-completeness proof of existence of stable models for uni-rule programs, (4) the application of the well-founded and stable semantics to a related subdiscipline of artificial intelligence, inductive logic programming.; Limiting the number of times a variable appears in either the head or the body of a rule, we identify five classes of normal propositional logic programs. These classes have the desirable property that stable models, if they exist, can be found in linear time (worst case). This work is presented in Chapters 4 and 5. In Chapter 6 we identify a related class containing programs for which the well-founded model can be acquired in linear time, yet for which computing the stable model(s) remains NP-complete. We show in Chapter 7 how, by relaxing one constraint of this class, previously linear complexity is increased to intractability. In Chapter 8, two new classes of unit programs, and another class of uni-rule programs (different from the class presented in Chapter 4) are found. It is then proved that these, too, have the property of linear time determination of stable models.; In Chapter 9 we introduce stable ILP, a cross-disciplinary concept straddling machine learning and nonmonotonic reasoning. It is here that we apply stable and well-founded models to real world applications. In Chapter 10 we present a description of the author's implementation of stable-ILP in system INDED.