Dynamic Worlds APPLIED LOGIC SERIES VOLUME12 Managing Editor Dov M. Gabbay, Department of Computer Science, King's College, London, U.K. Co-Editor Jon Barwise, Department of Philosophy, Indiana University, Bloomington, IN, U.SA. Editorial Assistant Jane Spurr, Department of Computer Science, King's College, London, U.K. SCOPE OF THE SERIES Logic is applied in an increasingly wide variety of disciplines, from the traditional subjects of philosophy and mathematics to the more recent disciplines of cognitive science, computer science, artificial intelligence, and linguistics, leading to new vigor in this ancient subject. Kluwer, through its Applied Logic Series, seeks to provide a home for outstanding books and research monographs in applied logic, and in doing so demonstrates the underlying unity and applicability of logic. The titles published in this series are listed at the end of this volume. Dynamic Worlds From the Frame Problem to Knowledge Management edited by REMO PARESCHI Xerox Research Centre Europe, Meylan, France and BERTRAM FRONHOFER Technische Universitat Miinchen Germany SPRINGER-SCIENCE+BUSINESS MEDIA, B.V. A C.I.P. Catalogue record for this book is available from the Library of Congress. ISBN 978-90-481-5159-2 ISBN 978-94-017-1317-7 (eBook) DOI 10.1007/978-94-017-1317-7 Logo design by L. Rivlin Printed on acid-free paper All Rights Reserved © 1999 Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers in 1999 Softcover reprint of the hardcover 1st edition 1999. No part of the material protected by this copyright notice may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage and retrieval system, without written permission from the copyright owner EDITORIAL PREFACE This volume deals with actions change and updates. This area is more than central in non-classical logic. Given the way applied logic is devel oping at the moment, it is likely that these subjects become dominant in the area. It is clear that in real applications, reasoning is intermingled with actions. Since reasoning is non-monotonic, additional information can knock down assumptions and invalidate conclusions. Additional data can therefore destroy the basis of preconditions of actions. In modelling real reasoning/action situations we need to address a typical proof-action-proof-action cycle which goes as follows: To prevent action b from happening, try and destroy its preconditions. To achieve that, try and (non-monotonically) derive the preconditions of action a and its post conditions will revise the (non-monotonic) database and from the revised version the preconditions of b are no longer deriv able. Thus non-monotonic proof theory, actions, time and revision all get mingled together! We welcome this volume to our series. D.M.Gabbay CONTENTS Preface ix NARCISO MARTi-OLIET AND JOSE MESEGUER Action and Change in Rewriting Logic 1 MICHAEL WOLLOWSKI AND ERIC HAMMER Heterogeneous Systems for Modeling Dynamic Worlds 55 CHITTA BARAL, MICHAEL GELFOND AND RICHARD WATSON Reasoning about Actual and Hypothetical Occurrences of Concurrent and Non-Deterministic Actions 73 DOV M. GABBAY Compromise Update and Revision: A Position Paper 111 FATIMA C. C. DARGAM A Compromise Revision Model for Reconciling Updates 149 JINXIN LIN AND ALBERTO 0. MENDELZON Knowledge Base Merging by Majority 195 ELISA BERTINO, GIOVANNA GUERRINI AND LUCA RUSCA Object Evolution in Object Databases 219 ULRICH REIMER, ANDREAS MARGELISCH AND BERND NOVOTNY Making Knowledge-Based Systems more Manageable: A Hybrid Integration Approach to Knowledge about Actions and their Legality 24 7 PREFACE Reasoning or drawing conclusions is an integral part of many software systems in important fields like data bases, logic programming, robotics, knowledge engineering, human/ computer interfaces, programming environ ments, etc. In reality any such system has to cope with a changing world and its dynamics. Hence it is of high importance that reasoning must ac count for coping with change in order to be truly useful in practice. The book comprises several contributions to current ways of approaching this problem. In the paper by Narciso Marti-Oliet and Jose Meseguer rewriting logic is proposed as a logic of concurrent action and change that solves the frame problem and that subsumes and unifies a number of previous log ics of change, including linear logic and Horn logic with equality. Rewriting logic can represent action and change with great flexibility and generality. This flexibility is illustrated by many examples, including examples that show how concurrent object-oriented systems are naturally represented. In addition, rewriting logic has a simple formalism, with only a few rules of de duction: It supports user-definable logical connectives, which can be chosen to fit the problem at hand, it is intrinsically concurrent and it is realizable in a wide spectrum logical language (Maude and its MaudeLog extension) supporting executable specification and programming. The paper by Michael Wollowski and Eric Hammer presents a diagram matic representational system that is designed to deal with the inferential complexities of a particular dynamic world, that of planning in a blocks world. It gives a rigorous syntax for the diagrams and a situation theoretic semantics modelling the domain in question. It also presents a sound and complete set of rules of inference for proving whether or not there is a plan that leads to some desired final state, given some initial state and various constraints about the world and possible transformations. The diagrams incorporate some of the constraints holding in the domain, thereby allevi ating inferential complexity. By making some modifications to the system, one may even further speedup inferential tasks. Finally, some theoretical problems surrounding the use and application of formal systems of diagrams in artificial intelligence are discussed and these problems are compared to those of language oriented systems. In the paper by Chitta Baral, Michael Gelfond and Richard Watson an extension £2 of the action description language £1 is proposed. It allows to express both actual and hypothetical situations, concurrent execution of actions, observations of the truth values of fluents in these situations (as op posed to hypothetical values of fluents expressible in the earlier languages A ix X and Ac ), observations of actual occurrences of (possibly non-deterministic combination of) actions. The corresponding entailment relation formalizes various types of common-sense reasoning about actions and their effects not modeled by the previous approaches. Finally a translation of domain descriptions in £2 to disjunctive logic programs is given. The paper by Dov M. Gabbay proposes a refined approach to belief re vision which is called Compromise Revision. Suppose we want to add a consistent well-formed formula C to a consistent database OC and suppose it cannot be accepted because OC U { C} is not consistent. In this case it is proposed that we do not necessarily either reject C or revise ][{, but to 'compromise' instead, whereby some of the consequences of C are put into OC (though not C itself) and thus a consistent 'compromise theory' OC + C is obtained. In addition, a compromise revision framework for arbitrary logics (not necessarily classical logic) and for Labelled Deductive Systems is discussed. The paper by Fatima C. C. Dargam presents a specific compromise based model to knowledge base revision. A model for reconciling logically conflicting inputs into knowledge bases is proposed, by choosing some of their consequences. The database is updated with as many consistent con sequences of the inputs as possible, while rejecting the inputs. Should a revision apply, as many as possible of the consistent consequences of the retracted sentences are kept as a compromise. Non-relevant consequences, such as unwanted disjunctions involving all the sentences of the language, are avoided. This approach provides an application-specific mechanism for knowledge base revision. It caters for those applications where compromise solutions make practical sense. The paper by Jinxin Lin and Alberto 0. Mendelzon deals with resolv ing conflicts among a group of agents. A common practice is to let the majority decide. This principle is formalized and appled to the problem of merging the knowledge of multiple agents. Logical properties that all knowledge merging operators should satisfy are postulated and a model theoretic characterization of all merging operators that satisfy the postu lates is given. It turns out that the operators that satisfy the postulates are precisely those that induce a certain kind of partial pre-order over the set of possible worlds such that the models of the merged knowledge base are the possible worlds that are 'minimal' with respect to the pre-order. Sev eral previous approaches are reviewed and analysed in light of the proposed postulates. Next a particular method for knowledge merging, CMerge, is presented which satisfies all the postulates. It is shown by example that CMerge appears to resolve conflicts among knowledge bases in a plausible way. Finally, it is shown that CMe rge can be implemented by an efficient syntactical transformation from the set of knowledge bases to be merged. The paper by Elisa Bertino, Giovanna Guerrini and Luca Rusca deal with evolution in object-oriented databases. In this area two different forms xi of evolution can be distinguished, evolution of schema and evolution of instances. The paper focuses on the latter in the context of the Chimera object-oriented deductive data model. In particular, problems related to object migration, dynamic object classification and multiple class direct membership are discussed. The paper by Ulrich Reimer, Andreas Margelisch and Bernd Novotny presents EULE2, a knowledge-based decision support system for office tasks. After motivating the need for such a system, the paper sketches its func tionality and discusses the three main knowledge sources it makes use of: terminological knowledge, knowledge about actions, and knowledge about federal law and company regulations. The terminological knowledge pro vides all the concepts relevant in the domain of discourse, and allows to introduce instances of those concepts. Knowledge about actions serves two purposes: to determine what changes have to be made when executing an action, and to decide what actions can or cannot be performed at a certain point in an office task. A representation formalism that satisfies both, quite heterogeneous requirements is described in detail. Knowledge about federal law and company regulations is needed to ensure that all office tasks are properly executed-this is the main functionality offered by EULE2. Sub sequently, the paper deals with how to properly integrate knowledge about law and regulations with the knowledge about actions. For this purpose a hybrid integration approach is proposed that keeps the representation of both kinds of knowledge independent from each other but ensures that the reasoning takes all relevant pieces of knowledge into account. It is ar gued that the resulting, hybrid integration approach drastically increases maintainability and reusability of knowledge bases as compared to former approaches. Remo Pareschi Bertram Fronh6fer NARCISO MARTi-OLIET AND JOSE MESEGUER ACTION AND CHANGE IN REWRITING LOGIC 1 INTRODUCTION After making precise what we mean and do not mean by "the frame prob lem" and discussing some recent approaches, we summarize the main fea tures of the solution offered by rewriting logic. 1.1 What the frame problem {in our sense) is Since the frame problem has been the subject of much controversy and unfortunately means different things to different people, any paper touching upon the subject runs the risk of unintentionally increasing confusion. The best way out of this danger is to state in plain English right at the beginning what we mean by "the frame problem." In this way, any objection to our arguments that is based on a different meaning of the words can then be dismissed as a failure to understand the terms of the discussion. In our sense, the frame problem [41, 27, 30] consists in formalizing the assumption that facts about a situation are preserved by an action unless the action explicitly says that a certain fact becomes true or false. In the words of Patrick Hayes [27, p. 125], "There should be some economical and principled way of suc cintly saying what changes an action makes, without having to explicitly list all the things it doesn't change as well [. .. ]. That is the frame problem." In our view, the heart of the frame problem is the essential inadequacy of standard logics for dealing with action and change. The term "standard" is used here in a fairly wide sense that includes not only first-order logic, but also higher-order logics and constructive type theories with the exception of linear logic [19]. The reasons for this inadequacy are fundamental, and have to do with the essentially Platonic nature of standard logics. Because those logics were developed as tools in the foundations of mathematics and were therefore designed to reason about unchanging entities such as numbers or geometric figures, it should come as no surprise that they deal very poorly with action and change. 1.2 What the frame problem {in our sense) is not In some very wide sense of the term "frame problem," by insisting on a perfectly accurate modelling or simulation of systems in the real world, the R. Pareschi and B. Fronhiifer (eds.), Dynamic Worlds, 1-53. © 1999 Kluwer Academic Publishers.