KR Conference 2012 Conference Paper
Update is a belief change operation that consists of bringing a knowledge base up to date when the world it describes changes (Winslett 1990; Katsuno and Mendelzon 1991). The study of update operators commenced with the introduction of KM postulates for update (Katsuno and Mendelzon 1991). Though the desirability of half of the eight KM postulates has later been questioned by many (Brewka and Hertzberg 1993; Boutilier 1995; Doherty, Lukaszewicz, and Madalinska-Bugaj 1998; Herzig and Rifi 1999), the fourth postulate, that we refer to as syntax-independence, is generally considered very desirable as it guarantees that insignificant syntactic differences in the representation of knowledge do not affect the result of an update (Herzig and Rifi 1999). Updates were later studied in the context of AnswerSet Programs. Earlier methods were based on literal inertia (Marek and Truszczynski 1998) but proved not sufficiently expressive. Though the state-of-the-art approaches are guided by the same basic intuitions and aspirations as belief update, they build upon fundamentally different principles and methods. While many are based on the causal rejection principle (Leite and Pereira 1997; Alferes et al. 2000; Eiter et al. 2002; Alferes et al. 2005; Osorio and Cuevas 2007), others employ syntactic transformations and other methods, such as abduction (Sakama and Inoue 2003), forgetting (Zhang and Foo 2005), prioritisation (Zhang 2006), preferences (Delgrande, Schaub, and Tompits 2007), or dependencies on defeasible assumptions (Šefránek 2011; Krümpelmann 2012). Despite the variety of techniques used in these approaches, certain properties are common to all of them. First, the stable models assigned to a program after one or more updates are always supported: for each true atom p there exists a rule in either the original program or its updates that has p in the head and whose body is satisfied. Second, all mentioned rule update semantics coincide when it comes to updating sets of facts by newer facts. We conjecture that any reasonable rule update semantics should indeed be in line with the basic intuitions regarding support and fact update. But in difference to belief update, rule updates exercise rule inertia instead of literal inertia. Rather than operating on the models of a logic program, they refer to its syntactic structure: the individual rules and, in many cases, also the literals in heads and bodies of these rules. These properties render them seemingly irreconcilable with belief update Existing methods for dealing with knowledge updates differ greatly depending on the underlying knowledge representation formalism. When Classical Logic is used, update operators are typically based on manipulating the knowledge base on the model-theoretic level. On the opposite side of the spectrum stand the semantics for updating Answer-Set Programs where most approaches need to rely on rule syntax. Yet, a unifying perspective that could embrace all these approaches is of great importance as it enables a deeper understanding of all involved methods and principles and creates room for their cross-fertilisation, ripening and further development. This paper bridges these seemingly irreconcilable approaches to updates. It introduces a novel monotonic characterisation of rules, dubbed RE-models, and shows it to be a more suitable semantic foundation for rule updates than SE-models. A generic framework for defining semantic rule update operators is then proposed. It is based on the idea of viewing a program as the set of sets of RE-models of its rules; updates are performed by introducing additional interpretations to the sets of RE-models of rules in the original program. It is shown that particular instances of the framework are closely related to both belief update principles and traditional approaches to rule updates and enjoy a range of plausible syntactic as well as semantic properties.