An extension of explanation-based generalization to negation as failure

Implementations of Explanation-Based Generalization (EBG) within a logic-programming environment, as e.g. the well-known PROLOG-EBG algorithm [KCMcC87], are able to generalize the proof of a goal from a definite (i.e. Horn clause) domain theory. However, it is a fact that practical applications frequently require the enhanced expressiveness of negations in rule bodies. Specifically, this is the case for the domain of game playing, where traditional EBG has turned out to be inadequate [Ta89]. In this paper we present an approach which extends EBG to this more general setting; it is described in the form of a transformation system, and comprises Siqueira and Puget's method of Explanation-Based Generalization of Failures [SiPu88] for definite programs. For the case that both domain theory and training example are represented as allowed normal programs, we prove that the derived clause satisfies the standard requirements of EBG, namely operationality, sufficiency, and correctness. Furthermore, a meta-interpreter implementation is given. (orig.)Available from TIB Hannover: RR 5165(66) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman