Research on Inverse Entailment in Nonmonotonic Logic Programming

点击翻译按钮获取中文摘要

In this research, we propose techniques for realizing induction in nonmonotonic logic programming. We first introduce an algorithm to induce hypotheses by inverting entailment. Next, we introduce a method for computing inductive hypotheses using answer sets in nonmonotonic logic programming. Further details are explained as follows.1. Inverse entailment (IE) is known as a basic technique for induction, which deductively constructs inductive hypotheses in clausal logic programs. When a background theory is a nonmonotonic logic program, however, the present IE technique cannot be used. The primary reason is that IE is based on the deduction theorem in first-order logic, which does not hold in nonmonotonic logics in general. To solve the problem, we establish a new entailment theorem in nonmonotonic logic programs. We construct a theory of IE in nonmonotonic ILP and present an induction algorithm to learn nonmonotonic logic programs from positive and negative examples.2. Answer set programming (ASP) is a new paradigm of logic programming which attracts much attention recently. ASP views a program as a set of constraints which every solution should satisfy, then extracts solutions from the collection of answer sets of the program. In this research we show a method of constructing inductive hypotheses using answer sets. In this setting, the background theory and examples work as constraints which inductive hypotheses should satisfy, and induction in nonmonotonic logic programs is realized by computing answer sets of a program. The result implies that induction based on inverse entailment is computable by proof procedures for answer set programming in nonmonotonic logic programming.