Updates of deductive knowledge bases

We are continuously faced with the need to update the knowledge that we possess. Performing frequent updates allows us to learn new facts and discard those that no longer apply. One can reasonably argue that most, if not all, of our knowledge is acquired via suitable sequences of updates. By extension, the same applies to intelligent artifacts, such as intelligent knowledge bases and intelligent agents. However, performing meaningful updates is by no means a trivial task. First of all, we have to be able to properly represent our knowledge and provide it with a precise meaning or semantics. Intelligent artifacts, such as databases and intelligent agents, must be provided with a mathematically precise representation of the knowledge. Moreover, such knowledge must be represented in a manner, which is independent of procedural considerations, easy to communicate, exchange and reason about. We must be able to handle updates in a dynamically changing world and thus we have to decide how to resolve contradictions arising from new updates. Quite often, adding a new fact or a new rule to our knowledge base forces us to remove some other facts or rules that are inconsistent with the newly acquired information. At the same time, we want to make sure that the set of facts that need to be revised or outright deleted is, in some precise sense, minimal. Finally, we need to choose between different approaches to and types of updates. After all, updates were quite extensively studied in the literature for a number of years now. In this presentation, I will describe updates using the so-called interpretation or possible world approach. We will show how a commonsense version of Newton’s principle of inertia can be used to provide an elegant and simple characterization of such updates which properly subsumes the important class of revision programs, due to Marek and Truszczynski [MT, MT2], and the formula update approach, due to Winslett [W]. The presentation is intended to be introductory and accessible to non-experts. Consequently, it will only touch upon the important issues involved. The presented results were obtained jointly with Hudson Turner. For details we refer the reader to our joint paper [PT] and to subsequent papers on dynamic logic programs [APPP, ALPPP].

Nieustannie stajemy przed koniecznością uaktualniania wiedzy, którą już posiadamy. Przeprowadzanie częstych aktualizacji pozwala nam poznać nowe fakty i odrzucić te, które już nie znajdują zastosowania. W artykule opisano sposoby uaktualniania wiedzy przy użyciu podejścia zwanego interpretacją lub światem możliwym. Pokazano jak można wykorzystać zdroworozsądkową wersję newtonowskiej zasady bezwładności do scharakteryzowania w sposób elegancki i prosty powyższych uaktualnień, co właściwie podsumowuje istotną klasę programów adiustacyjnych (za Wiktorem Markiem i Mirosławem Truszczyńskim) i podejście uaktualniania formuł (za Marianne Winslett).