Lecture Notes in Artificial Intelligence 927 Subseries of Lecture Notes in Computer Science Edited by iJ G. Carbonell and J. Siekmann Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis and J. van Leeuwen Jtirgen Dix Louis Moniz Pereira Teodor C. Przymusinski (Eds.) Non-Monotonic Extensions of Logic gnimmargorP ICLP '94 Workshop Santa Margherita Ligure, Italy, June ,71 1994 Selected Papers regnirpS Series Editors Jaime G. Carbonell School of Computer Science Carnegie Mellon University Pittsburgh, AP 15213-3891, USA J~rg Siekmann University of Saarland German Research Center forArtificial Intelligence (DFKI) Stuhlsatzenhausweg 3, D-66123 Saarbriicken, Germany Volume Editors Jiirgen Dix Institut fiir Informatik, Universit~it Koblenz-Landau Rheinau ,1 D-56075 Koblenz, Germany Louis Moniz Pereira Departamento de Inform~ttica, Universidade Nova de Lisboa P-2825 Monte da Caparica, Portugal Teodor Przymusinski Department of Computer Science, University of California Riverside, CA 92521, USA CR Subject Classification (1991): 1.2.3, F.4.1, D.1.6 ISBN 3-540-59467-1 Springer-Verlag Berlin Heidelberg New York CIP data applied for This work is subject to copyright.All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. (cid:14)9 Springer-Verlag Berlin Heidelberg 1995 Printed in Germany Typesetting: Camera ready by author SPIN: 10486216 .06/3142-543210 - Printed on acid-free paper Preface This book is the outcome of an original compilation of extended and revised versions of selected papers presented at the workshop on Non-Monotonic Exten- sions of Logic Programming, held in Santa Margherita Ligure, Italy, on June ,71 1994. It also includes additional papers solicited from the participants. As some workshop papers were published elsewhere, they do not appear in this volume. The workshop on Non-Monotonic Extensions to Logic Programming was or- ganized in conjunction with ICLP '94, the Eleventh International Conference on Logic Programming. It was the fourth in a series of workshops held jointly with logic programming conferences (NACLP'90, ILPS'91, and ILPS'93) and received financial support from the ESPRIT Network of Excellence Compulog-Net and the University of Koblenz. The motivation for these workshops stems from the fact that during the last decade a significant body of knowledge has been accumulated providing us with a better understanding of the semantic issues in logic programming and the theory of deductive databases. In particular, the class of perfect models for (locally) stratified logic programs and two closely related extensions to normal, non-disjunctive, logic programs were introduced and extensively investigated: the well-founded models and the stable models. Semantics of logic programs rely on a non-monotonic operator, often referred to as negation-by-failure or negation-by-default. The non-monotonicity of this operator allows us to view logic programs as special non-monotonic theories and thus makes it possible to draw from the extensive research in the area of non-monotonic reasoning and use it as a guidance in the search for a suitable semantics for logic programs. Furthermore, the problem of extending the well-founded and the stable mod- els approaches, by defining a suitable semantics for normal and disjunctive pro- grams extended with a second type of negation, turned out to be a difficult one, as evidenced by a large number of papers devoted to the subject. As a result, research work aimed at better understanding of the relation- ships existing between logic programming (LP) and a variety of nonmonotonic formalisms (NMF) has been mutually beneficial to both areas. NMFs help us to determine suitable semantics for logic programs and they help us as well to understand how they can be applied to express and solve various AI problems. Conversely, the NMFs can utilize the wide body of knowledge already gathered about LP and use logic programs as inference engines for query answering. The 01 papers in this collection address the issues stemming from this out- look. Because new semantics often require new computational procedures, the papers can be naturally divided into two sections: Semantics 5( papers) and Computation 5( papers). We give more specific comments about the papers and their interrelationship in the Introduction (page .)1 IV All contributions were refereed by the Program Committee members, who are all to be thanked for their invaluable help and effort. Thanks are due as well to the external reviewers (see next page). Last but not least, let us congratulate all the authors, whose high quality research and text formatting abilities made this book a reality. We are sure it will spur on further research into this exciting and open field. March 1995 Jfirgen Dix, Koblenz Luis Moniz Pereira, Lisboa Teodor C. Przymusinski, Riverside Previous Workshops 0991 WS at NACLP '90, U.S.A. 1991 WS at ILPS '91, U.S.A. 3991 WS at ILPS '93, U.S.A. 1994 WS at ICLP '94, Italy Sponsors Compulog Network of Excellence, University of Koblenz. Organizing Committee Jiirgen Dix University of Koblenz Luls Moniz Universidade Nova di Lisboa Teodor Przymusinski University of California at Riverside Program Committee Jiirgen Dix University of Koblenz, Germany Michael Gelfond University of Texas at 1E Paso, U.S.A. Jorge Lobo University of Illinois at Chicago, U.S.A. Wiktor Marek University of Kentucky at Lexington, U.S.A. Luis Moniz Pereira Universidade Nova di Lisboa, Portugal Teodor Przymusinski University of California at Riverside, U.S.A. Additional Referees J.J. Alferes, C.V. Damasio, L. Degerstedt, A. Provetti, and Carlos Uzc~tegui. Table of Contents Introduction ............................................................... 1 Semantics An Argumentation Theoretic Semantics Based on Non-Refutable Falsity .... 3 J.J. Alferes and L.M. Pereira From Disjunctive Programs to Abduction ................................. 23 .V Lifschitz and .H Turner Semantics of Normal and Disjunctive Logic Programs: A Unifying Framework ................................................... 43 ."7 .C Przymusinski Every Normal Program has a Nearly-Stable Model ........................ 68 .C Witteveen Logic Programming with Assumption Denial .............................. 85 J.-H. You and L.Y. Yuan Computation A Resolution-based Procedure for Default Theories with Extensions ...... 101 M.D. Barback and J. oboL A General Approach to Bottom-Up Computation of Disjunctive Semantics ................................................... 127 S. Brass and J. Dix Static Semantics as Program Transformation and Well-founded Computation .............................................. 156 S. Costantini and G.A. Lanzarone Magic Computation for Well-founded Semantics ......................... 181 L. Degersledl and .U Nilsson Computing Stable and Partial Stable Models of Extended Disjunctive Logic Programs ................................ 205 C. Ruiz and J. Minker Introduction In order to facilitate reading this book, we now give a brief overview of the contents of the presented papers. We follow our classification of papers into two categories, one devoted to semantics and the other to computation. Semantics: While Alferes/Pereira as well as Witteveen deal with extended normal programs, all other papers in this section deal with extended disjunctive programs. The first paper, An argumentation theoretic semantics on based non-refutable falsity by J. J. Alferes and L. M. Pereira, extends previous works of the authors (O-semantics) by presenting a new semantics for extended logic programs. The intuition behind is that the well-founded semantics often is overly careful in deciding about the falsity of some atoms by leaving them undefined. Default literals are viewed as arguments a rational agent can sustain along with the program. The second paper, From Disjunctive Programs to Abduction by V. Lifschitz and H. Turner, deals with the problem of representing incomplete information using different formalisms (classical negation and epistemic disjunction versus two variants of abductive logic programming). Three formalisms are applied to a particular action-domain (the Yale Shooting) and the presented results show that they are very closely related (by simple syntactic transformations). The third paper, Semantics of Normal and Disjunctive Logic Programs: A unifying framework by T. Przymusinski, introduces a uniform semantic frame- work that isomorphically contains the major semantics for normal, disjunctive and extended logic programs. The framework is based on the Autoepistemic Logic of Knowledge and beliefs, AELB, introduced recently by the author. C. Witteveen's paper, Every Normal Program has a Nearly-Stable Model, investigates the inconsistency-problem of the stable semantics: stable models need not always exist. He presents two simple syntactic transformations, shifting and condensation that allow to transform any program in another one having at least one stable model. The last paper in the Semantics group, Logic Programming with Assumption Denial by J.-H. You and L.-Y. Yuan, deals with arbitrary extended disjunctive programs. The authors define a framework which allows to explicitely represent defeats of assumptions, so called assumption denials. Their method is related to abduction and reveals interesting relationships between disjunctive and non- disjunctive programs. Computation: With the exception of the first, all remaining papers deal with transformations. Different syntactical transformations are applied to the originM program to obtain a certain normal form which is used to compute the semantics more efficiently. While Degerstedt/Nilsson consider the well-founded semantics, the other authors compute (partial) stable models or the static se- mantics for disjunctive programs. The first paper of this section, A Resolution-based Procedure for Default Theories with Extensions by M. Barback and J. Lobo, deals with a problem in general non-monotonic reasoning: to determine if a given formula is true in all (sceptical entailment) or in some (credulous entailment) extensions of a default theory. The authors relate this problem to logic programming, by defining a sound and complete proof-procedure that is closely related to SLDNF and abduction-like procedures for logic programs. In the second paper, A General Approach to Bottom-Up Computation of Disjunctive Semantics by St. Brass and J. Dix, a method for deriving bottom- up query evaluation algorithms from the abstract properties of the underlying negation semantics is described. An important ingredient is to derive first the residual program (using partial evaluation and reductions). The authors argue that this approach is applicable to a large class of disjunctive semantics, like the stable, and the static semantics and its variants. The next paper, Static Semantics as Program Transformation and Well- founded Computation by S. Costantini and G. Lanzarone, describes a general framework of computing semantics for disjunctive logic programs that are similar to the static semantics. They distinguish between a program transformation phase, which absorbs most of the complexity and a constructive phase, which is similar to the well-founded computation for normal programs. The paper by L. Degerstedt and U. Nilsson, Magic Computation for Well- founded Semantics, deals with non-disjunctive semantics under the well-founded semantics. The authors introduce a new magic templates transformation and show a step-by-step correspondence between the naive bottom-up evaluation of the transformed program and a class of top-down search strategies. They show their method to be sound and complete. Finally, the last paper of this book, Computing Stable and Partial Stable Models of Extended Disjunctive Logic Programs by C. Ruiz and J. Minker, again deals with extended disjunctive logic programs. The authors describe a proce- dure to compute the collection of all partial stable models of a program. This is done by transforming the program into a constrained disjunctive program without any non-monotonic negation such that the classical minimal models of the transformed program correspond to the set of partial stable models of the original program. An argumentation theoretic semantics based on non-refutable falsity* Jos~ 3dlio Alferes 1 and Luis Moniz Pereira 2 1 DMAT, Universidade de ~vora and CRIA, Uninova 2825 Monte da Caparica, Portugal [email protected] 2 DCS, U. Nova de Lisboa and CR.IA, Uninova 2825 Monte da Caparica, Portugal [email protected] Abstract. We contend that the well-founded semantics (WFS), for nor- mal program, and similarly the well-founded semantics with explicit ne- gation (WFSX), for extended ones are, by design, overly careful in deci- ding about the falsity of some atoms, by leaving them undefined. We've dealt with this issue in normal programs and have previously defined the O-semantics, one that extends WFS by addjoining to it more negative assumptions, at the expense of undefined literals. The goal of this paper is to generalize that work to extended programs, and define a semantics for such programs that enlarges WFSX with more negative assumptions. To achieve this we view default literals as arguments a rational agent can sustain along with the program. As our goal is to enlarge WFSX, we consider the latter as the common reasoning ground and argumentation of agents. tool With this basis, and in order to define the semantics, we first formalize the concepts of consistent and non-refutable sets of arguments (or of hypotheses). In general several such sets may exist. So, and in order to define a unique semantics, given by a single set of additional assumpti- ons, we introduce an additional non-refutability of arguments criterium tenability - for always and finally preferring just one set of arguments - over another. 1 Introduction The Well Founded Semantics (WFS) GRS91 has been proposed as a suitable semantics for normal logic programs. Unlike other semantics, WFS gives mea- ning to every normal program, is cumulative Dix91, and can be obtained by a bottom-up fixpoint construction. Because it is a relevant semantics Dix92 it is susceptible of top-down existencial query procedures. However, as argued in KM91, PAA92a, PAA93, the WFS is by design overly careful in deciding about the falsity of some atoms, leaving them undefined. * We thank Esprit BR project Compulog 2 (no. 6810) for its support.