A Framework for Declarative Update Specifications in Logic Programs

1 Introduction

Updating knowledge bases is an important issue for the realization of intelligent agents, since, in general, an agent is situated in a changing environment and must adjust its knowledge base when new information is available. While for classical knowledge bases this issue has been well-studied, approaches to update nonmonotonic knowledge bases, like, e.g., updates of logic programs [Alferes et al., 2000; Eiter et al., 2000; Zhang and Foo, 1998; Inoue and Sakama, 1999] or of default theories [Williams and Antoniou, 1998], are more recent.

The problem of updating logic programs, on which we focus here, deals with the incorporation of an update , given by a rule or a set of rules, into the current knowledge base BU. Accordingly, sequences  BD BN BM BM BM BN  D2 of updates lead to sequences B4BUBN  BD BN BM BM BM BN  D2 B5 of logic programs, which are given a declarative semantics. To broaden this approach, Alferes et al. [1999a] have proposed the LUPS update language, in which updates consist of sets of update commands. Such commands permit to specify changes to BU in terms of adding or removing rules from it. For instance, a typical command is CPD7D7CTD6D8 CP AW CQ DBCWCTD2 CR, stating that rule CP AW CQ should be added to BU if CR is currently true in it. Similarly, D6CTD8D6CPCRD8 CQ expresses that CQ must be eliminated from BU, without any further condition.

However, a certain limitation of LUPS and the above mentioned formalisms is that while they handle ad hoc changes of BU, they are not conceived for handling a yet unknown update, which will arrive as the environment evolves. In fact, these approaches lack the possibility to specify how an agent should react upon the arrival of such an update. For example, we would like to express that, on arrival of the fact CQCTD7D8 CQD9DDB4D7CWD3D4 BD B5, this should be added to BU, while bestbuy information about other shops is removed fromBU.

In this paper, we address this issue and present a declarative framework for specifying update behavior of an agent. The agent receives new information in terms of a set of rules (which is called an event), and adjusts its BU in accord to a given update policy, consisting of statements in a declarative language. Our main contributions are summarized as follows:

1. We present a generic framework for specifying update behavior, which can be instantiated with different update approaches to logic programs. This is facilitated by a layered approach: At the top level, the update policy is evaluated, given an event and the agent's current belief set, to single out the update commands CD which need to be performed on BU. At the next layer, CD is compiled to a set  of rules to be incorporated to BU; at the bottom level, the updated knowledge base is represented as a sequence of logic programs, serving as input for the underlying update semantics for logic programs, which determines the new current belief set.
2. We define a declarative language for update policies, generalizing LUPS by various features. Most importantly, access to incoming events is facilitated. For example, retractB4CQCTD7D8 CQD9DDB4D7CWD3D4 BD B5B5 CJCJBX BM CQCTD7D8 CQD9DDB4D7CWD3D4 BE B5CLCL states that if CQCTD7D8 CQD9DDB4D7CWD3D4 BE B5 is told, then CQCTD7D8 CQD9DDB4D7CWD3D4 BD B5 is removed from the knowledge base. Statements like this may involve further conditions on the current belief set, and other commands to be executed (which is not possible in LUPS). The language thus enables the flexible handling of events, such as simply recording changes in the environment, skipping uninteresting updates, or applying default actions.

(3) We analyze some properties of the framework, using the update answer set semantics of Eiter et al. [2000] as a representative of similar approaches. In particular, useful properties concerning BU maintenance are explored, and the complexity of the framework is determined. Moreover, we describe a possible realization of the framework in the agent system IMPACT [Subrahmanian et al., 2000], providing evidence that our approach is a viable tool for developing adaptive reasoning agents.

2 Preliminaries

We assume the reader familiar with extended logic programs (ELPs) [Gelfond and Lifschitz, 1991]. For a rule D6, we write B4D6B5 and BUB4D6B5 to denote the head and body of D6, respectively. Furthermore, D2D3D8 stands for default negation andBM for strong negation. CXD8 BT is the set of all literals over a set of atoms BT, and  BT is the set of all rules constructible from CXD8 BT .

An update program, P, is a sequence B4 BD BN BM BM BM BN  D2 B5 of ELPs, where D2 AL BD. We adopt an abstract view of the semantics of ELPs and update programs, given as a mapping BUCTD0B4A1B5, which associates with every sequence P a set BUCTD0B4PB5 AI  BT of rules; intuitively, BUCTD0B4PB5 are the consequences of P. Different instantiations of BUCTD0B4A1B5 are possible, according to various proposals for update semantics. We only assume that BUCTD0B4A1B5 satisfies some elementary properties which any "reasonable" semantics satisfies. In particular, we assume that  D2 AI BUCTD0B4PB5 holds, and that the following property is satisfied: given BT AW BE BUCTD0B4PB5 and BT BE BUB4D6B5, then D6 BE BUCTD0B4PB5 iff B4D6B5 AW BUB4D6B5 D2 CUBTCV BE BUCTD0B4PB5.

We use here the semantics of Eiter et al. [2000], which coincides with the semantics of inheritance programs due to Buccafurri et al. [1999]. The semantics of ELPs  and update sequences P with variables is defined as usual through their ground versions BZB4B5 and BZB4PB5 over the Herbrand universe, respectively. In what follows, let BT, , P, etc. be ground.

An interpretation is a set CB AI CXD8 BT which contains no complementary pair of literals. CB is a (consistent) answer set of an ELP  iff it is a minimal model of the reduct  CB , which results from  by deleting all rules whose body contains some default literal D2D3D8  with  BE CB, and by removing all default literals in the bodies of the remaining rules [Gelfond and Lifschitz, 1991]. By BTCBB4B5 we denote the collection of all answer sets of . The rejection set, CACTCY B4CBBN PB5, of P with respect to the interpretation CB is given by CACTCY B4CBBN PB5 BP CB D2 CXBPBD CACTCY CX B4CBBN PB5BN where CACTCY D2 B4CBBN PB5 BP BN, and, for D2 BQ CX AL BD, CACTCY CX B4CBBN PB5 contains every rule D6 BE  CX such that B4D6 BC B5 BP BMB4D6B5 and BUB4D6B5 CJ BUB4D6 BC B5 AI CB, for some D6 BC BE  CY D2 CACTCY CY B4CBBN PB5 with CY BQ CX. Then, CB is an answer set of P BP B4 BD BN BM BM BM BN  D2 B5 iff CB is an answer set of CB CX  CX D2CACTCY B4CBBN PB5. We denote the collection of all answer sets of P by BTCBB4PB5. Since D2 BP BD implies CACTCY B4CBBN PB5 BP BN, the semantics extends the answer set semantics. [Eiter et al., 2000] describes a characterization of the update semantics in terms of single ELPs.

Example 1 Let  BC BP CUCQ AW D2D3D8 CPBN CP AW CV,  BD BP CUBMCP AW BN CR AW CV, and  BE BP CUBMCR AW CV. Then,  BC has the single answer set CB BC BP CUCPCV with CACTCY B4CB BC BN  BC B5 BP BN; B4 BC BN  BD B5 has answer set CB BD BP CUBMCPBN CRBN CQCV with CACTCY B4CB BD BN B4 BC BN  BD B5B5 BP CUCP AWCV; and B4 BC BN  BD BN  BE B5 possesses CB BE BP CUBMCPBN BMCRBN CQCV as unique answer set with CACTCY B4CB BE BN B4 BC BN  BD BN  BE B5B5 BP CUCR AW BN CP AWCV.

The belief set BUCTD0 BT B4PB5 is the set of all rules D6 BE  BT such that D6 is true in each CB BE BTCBB4PB5. We shall drop the subscript "BT" if no ambiguity can arise. With a slight abuse of notation, for a literal , we write  BE BUCTD0 BT B4PB5 if  AW BE BUCTD0 BT B4PB5.

3 Update Policies

We first describe our generic framework for event-based updating, and afterwards the BX
language ("the language around") for specifying update policies.

3.1 Basic Framework

We start with the formal notions of an event and of the knowledge state of an agent.

Definition 1 An event class is a collection BXBV AI BE  BT of finite sets of rules. The members BX BE BXBV are called events.

Informally, BXBV describes the possible events (i.e., sets of communicated rules) an agent may witness. For example, the collection BY of all sets of facts from a subset BT BC AI BT of atoms may be an event class. In what follows, we assume that an event class BXBV has been fixed.

Definition 2 A knowledge state CB BP CWBUBNBX BD BN BM BM BM BNBX D2 CX consists of an ELP BU B4the initial knowledge base) and a sequence BX BD BN BM BM BM BN BX D2 of events BX CX BE BXBV, CX BE CUBDBN BM BM BM BN D2CV. For CX AL BC, CB CX BP CWBUBNBX BD BN BM BM BM BNBX CX CX is the projection of CB to the first CX events.

Intuitively, CB describes the evolution of the agent's knowledge, starting from its initial knowledge base. When a new event BX CX occurs, the current knowledge state CB CXA0BD changes to CB CX BP CWBUBNBX BD BN BM BM BM BNBX CXA0BD BNBX CX CX, which requests the agent to incorporate the event BX CX into its knowledge base and adapt its belief set.

The procedure for adapting the belief set BUCTD0B4CB CXA0BD B5 on arrival of BX CX is illustrated in Figure 1. Informally, at step CX of the knowledge evolution, we are given the belief set BUCTD0B4CB CXA0BD B5 and the knowledge state CB CXA0BD BP CWBUBNBX BD BN BM BM BM BNBX CXA0BD CX, together with the new event BX CX , and we want to compute BUCTD0B4CB CX B5 in terms of the update policy CD. First, a set CD CX of executable commands is determined from CD. Afterwards, given the previously computed sets CD BD BN BM BM BM BN CD CXA0BD , the sequence B4BUBN CD BD BN BM BM BM BN CD CX B5 is compiled by the transformation D8D6 into the update sequence P BP B4 BC BN  BD BN BM BM BM BN  CX B5. Then, BUCTD0B4CB CX B5 is given by BUCTD0B4PB5.

CWD7D8CPD8CX ::= CWCRD3D1D1CX CJCXCU CWCRD3D2CSBDCXCL CJCJCJCWCRD3D2CSBECXCLCLCL; CWCR D2CPD1CTCX ::= CPD7D7CTD6D8CJ CTDACTD2D8CL CY D6CTD8D6CPCRD8CJ CTDACTD2D8CL CY CPD0DBCPDDD7CJ CTDACTD2D8CL CY CRCPD2CRCTD0 CY CXCVD2D3D6CT ; CWD6 CXCSCX ::= CWD6D9D0CTCX CY CWD6 DACPD6CX; CWD0CXD8 CXCSCX ::= CWD0CXD8CTD6CPD0CX CY CWD0CXD8 DACPD6CX; CWCRD3D1D1CX ::= CWCR D2CPD1CTCXB4CWD6 CXCSCXB5 ; CWCRD3D2CSBDCX ::= CJD2D3D8CL CWCRD3D1D1CX CY CJD2D3D8CL CWCRD3D1D1CXBN CWCRD3D2CSBDCX ; CWCRD3D2CSBECX ::= CWCZCQ CRD3D2CSD7CX CY BX BM CWCTDA CRD3D2CSD7CX CY CWCZCQ CRD3D2CSD7CX , BX BM CWCTDA CRD3D2CSD7CX; CWCZCQ CRD3D2CSD7CX ::= CWCZCQ CRD3D2CSCX CY CWCZCQ CRD3D2CSCX , CWCZCQ CRD3D2CSD7CX; CWCZCQ CRD3D2CSCX ::= CWD6 CXCSCX CY CWD0CXD8 CXCSCX ; CWCTDA CRD3D2CSD7CX ::= CWCTDA CRD3D2CSCX CY CWCTDA CRD3D2CSCX , CWCTDA CRD3D2CSD7CX; CWCTDA CRD3D2CSCX ::= CWD0CXD8 CXCSCX CY CWD6 CXCSCX ;

3.2 Language BX
: Syntax

The language BX
generalizes the update specification language LUPS [Alferes et al., 1999a], by allowing update statements to depend on other update statements in the same BX
program, and more complex conditions on both the current belief set and the actual event (note that LUPS has no provision to support external events). These features make it suitable for implementing rational reactive agents, capable, e.g., of filtering incoming information.

The syntax of BX
is given in Table 1. In what follows, we use CRD1CS to denote update commands and AQ to refer to rules or rule variables. In general, an BX
statement may have the form

which states conditional assertion or retraction of a rule AQ BD , expressed by CRD1CS BD B4AQ BD B5, depending on other commands CJD2D3D8CLCRD1CS BE B4AQ BE B5BN . . . ,CJD2D3D8CLCRD1CS D1 B4AQ D1 B5, and conditioned with the proviso whether CR BD belongs to the current belief set and whether CR BE is in the actual event. The basic BX
commands are the same as those in LUPS (for their meaning, cf. [Alferes et al., 1999a]), plus the additional command ignore, which allows to skip unintended updates from the environment, which otherwise would be incorporated into the knowledge base. Each condition in CJCJA1CLCL, both of the form CR BD and BX BMCR BE , can be substituted by a list of such conditions. Note that in LUPS no conditions on rules and external events can be explicitly expressed, nor dependencies between update commands. We also extend the language by permitting variables for rules and literals in the update commands, ranging over the universe of the current belief set and of the current event (syntactic safety conditions can be easily checked). By convention, variable names start with capital letters.

Definition 3 An update policy CD is a finite set of BX
statements.

For instance, the BX
statement

means that all rules in the event have to be incorporated into the new knowledge base, except if it is explicitly specified that the rule is to be ignored. Similarly, the command retract forces a rule to be deactivated. The option event states that an assertion or retraction has only temporary value and is not supposed to persist by inertia in subsequent steps. The precise meaning of the different update commands will be made clear in the next section.

Example 2 Consider a simple agent selecting Web shops in search for some specific merchandise. Suppose its knowledge base, BU, contains the rules

D6 BD BM D5D9CTD6DDB4CBB5AW D7CPD0CTB4CBB5BN D9D4B4CBB5BN D2D3D8 BMD5D9CTD6DDB4CBB5BN D6 BE BM D8D6DD D5D9CTD6DD AWD5D9CTD6DDB4CBB5BN D6 BF BM D2D3D8CXCUDD AWD2D3D8 D8D6DD D5D9CTD6DDBN

and a fact D6 BC BM CSCPD8CTB4BCB5 as an initial time stamp. Here, D6 BD expresses that a shop CB, which has a sale and whose Web site is up, is queried by default, and D6 BE , D6 BF serve to detect that no site is queried, which causes 'D2D3D8CXCUDD' to be true. Assume that an event, BX, might be any consistent set of facts or ground rules of the form D7CPD0CTB4D7B5 AW CSCPD8CTB4D8B5, stating that shop D7 has a sale on date D8, such that BX contains at most one time stamp CSCPD8CT B4A1B5.

An update policy CD may be defined as follows. Assume it contains the incorporate-by-default statement B4BDB5, as well as:

CPD0DBCPDDD7B4D7CPD0CTB4CBB5 AW CSCPD8CTB4CC B5B5 CXCU CPD7D7CTD6D8B4D7CPD0CTB4CBB5 AW CSCPD8CTB4CC B5B5; CRCPD2CRCTD0B4D7CPD0CTB4CBB5 AW CSCPD8CTB4CCB5B5CJCJCSCPD8CTB4CCB5BN CC BIBP CC BC BN BX BM CSCPD8CT B4CC BC B5CLCL; D6CTD8D6CPCRD8B4D7CPD0CTB4CBB5 AW CSCPD8CTB4CCB5B5CJCJCSCPD8CTB4CCB5BN CC BIBP CC BC BN BX BM CSCPD8CT B4CC BC B5CLCL.

Informally, the first statement repeatedly confirms the information about a future sale, which guarantees that it is effective on the given date, while the second statement revokes this. The third one removes information about a previously ended sale B4assuming the time stamps increaseB5. Furthermore, CD includes also the following statements:

D6CTD8D6CPCRD8B4CSCPD8CTB4CCB5B5CJCJCSCPD8CTB4CCB5BN CC BIBP CC BC BNBX BM CSCPD8CTB4CC BC B5CLCL; CXCVD2D3D6CTB4D7CPD0CTB4D7 BD B5B5CJCJBX BM D7CPD0CTB4D7 BD B5CLCL; CXCVD2D3D6CTB4D7CPD0CTB4D7 BD B5 AW CSCPD8CTB4CC B5B5CJCJBX BM D7CPD0CTB4D7 BD B5 AW CSCPD8CTB4CC B5CLCL.

The first statement keeps the time stamp CSCPD8CTB4D8B5 in BU unique, and removes the old value. The other statements simply state that sales information about shop D7 BD is ignored.

3.3 Language BX
: Semantics

According to the overall structure of the semantics of BX
, as depicted in Figure 1, at step CX, we first determine the executable command CD CX given the current knowledge state CB CXA0BD BP CWBUBNBX BD BN BM BM BM BNBX CXA0BD CX and its associated belief set BUCTD0B4CB CXA0BD B5 BP BUCTD0B4P CXA0BD B5, where P CXA0BD BP B4 BC BN BM BM BM BN  CXA0BD B5. To this end, we evaluate the update policy CD over the new event BX CX and the belief set BUCTD0B4P CXA0BD B5.

Let BZB4CDB5 be the grounded version of CD over the language BT underlying the given update sequence and the received events. Then, the set BZB4CDB5 CX of reduced update statements at step CX is given by

The update statements in BZB4CDB5 CX are thus of the form CRD1CS BD B4AQ BD B5 CXCU CJD2D3D8CL CRD1CS BE B4AQ BE B5BN BM BM BM BN CJD2D3D8CL CRD1CS D1 B4AQ D1 B5. Semantically, we interpret them as ordinary logic program rules CRD1CS BD B4AQ BD B5 AW CJD2D3D8 CLCRD1CS BE B4AQ BE B5BN BM BM BM BN CJD2D3D8 CLCRD1CS D1 B4AQ D1 B5. The program A5 CD CX is the collection of all these rules, given BZB4CDB5 CX , together with the following constraints, which exclude contradictory commands:

AWCPD7D7CTD6D8CJ CTDACTD2D8CLB4CAB5BN D6CTD8D6CPCRD8CJ CTDACTD2D8CLB4CAB5BN AWCPD0DBCPDDD7CJ CTDACTD2D8CLB4CAB5BN CRCPD2CRCTD0B4CAB5BM

Definition 4 Let CB BP CWBUBNBX BD BN BM BM BM BNBX D2 CX be a knowledge state and CD an update policy. Then, CD CX is a set of executable update commands at step CX B4CX AK D2B5 iff CD CX is an answer set of the grounding BZB4A5 CD CX B5 of A5 CD CX .

Since update statements do not contain strong negation, executable update commands are actually stable models of BZB4A5 CD CX B5 [Gelfond and Lifschitz, 1988]. Furthermore, since programs may in general have more than one answer set, or no answer set at all, and the agent must commit itself to a single set of update commands, we assume a suitable selection function, CBCTD0 B4A1B5, returning a particular CD CX if an answer set exists, or, otherwise, returning CD CX BP CUCPD7D7CTD6D8B4BR CX AW B5CV, where BR CX is a reserved atom. These atoms are used for signaling that the update policy encountered inconsistency. They can easily be filtered out from BUCTD0B4A1B5, if needed, restricting the outcomes of the update to the original language.

Next we compile the executable commands CD BD BN BM BM BM BN CD CX into an update sequence B4 BC BN BM BM BM BN  CX B5, serving as input for the belief function BUCTD0B4A1B5. This is realized by means of a transformation D8D6B4A1B5, which is a generic and adapted version of a similar mapping introduced by Alferes et al. [1999a]. In what follows, we assume a suitable naming function for rules in the update sequence, enforcing that each rule D6 is associated with a unique name D2 D6 .

Definition 5 Let CB BP CWBUBNBX BD BN BM BM BM BN BX D2 CX be a knowledge state and CD an update policy. Then, for CX AL BC, D8D6B4BUBN CD BD BN BM BM BM BN CD CX B5 BP B4 BC BN  BD BN BM BM BM BN  CX B5 is inductively defined as follows, where CD BD BN BM BM BM BN CD CX are the executable commands according to Definition 4:

• CX BP BC BM Set  BC BP CUB4D6B5 AW BUB4D6B5BN D3D2B4D2 D6 B5 CY D6 BE BUCV CJ CUD3D2B4D2 D6 B5 AW CY D6 BE BUCV, where D3D2B4A1B5 are new atoms. Furthermore, initialize the sets BV BC of persistent commands and BXBV BC of effective commands to BN.

CX AL BD BM BXBV CX , BV CX and  CX are as follows: BXBV CX = CUCRD1CSB4D6B5 CY CRD1CSB4D6B5 BE CD CX CM CXCVD2D3D6CTB4D6B5 BPBE CD CX CV; BV CX = BV CXA0BD CJ CUCPD0DBCPDDD7B4D6B5 CY CPD0DBCPDDD7B4D6B5 BE BXBV CX CV CJ CUCPD0DBCPDDD7 CTDACTD2D8B4D6B5 CY CPD0DBCPDDD7 CTDACTD2D8B4D6B5 BE BXBV CX CM CPD0DBCPDDD7B4D6B5 BPBE BXBV CX CJ BV CXA0BD CV D2 B4CUCPD0DBCPDDD7 CTDACTD2D8B4D6B5 CY CPD0DBCPDDD7B4D6B5 BE BXBV CX CV CJ CUCPD0DBCPDDD7CJ CTDACTD2D8CLB4D6B5 CY CRCPD2CRCTD0B4D6B5 BE BXBV CX CVB5BN  CX = CUD3D2B4D2 D6 B5 AW BNB4D6B5 AWBUB4D6B5BN D3D2B4D2 D6 B5 CY CPD7D7CTD6D8CJ CTDACTD2D8CLB4D6B5 BE BXBV CX CN CPD0DBCPDDD7CJ CTDACTD2D8CLB4D6B5 BE BV CX CV CJ CUD3D2B4D2 D6 B5 AW CY D6CTD8D6CPCRD8 CTDACTD2D8B4D6B5 BE BXBV CXA0BD CM D6CTD8D6CPCRD8CJ CTDACTD2D8CLB4D6B5 BPBE BXBV CX CV CJ CUBMD3D2B4D2 D6 B5 AW CY B4D6CTD8D6CPCRD8CJ CTDACTD2D8CLB4D6B5 BE BXBV CX CM CPD0DBCPDDD7CJ CTDACTD2D8CLB4D6B5 BPBE BV CX B5 CN B4CPD0DBCPDDD7 CTDACTD2D8B4D6B5 BE BV CXA0BD CM CRCPD2CRCTD0B4D6B5 BE BXBV CX CM CPD7D7CTD6D8CJ CTDACTD2D8CLB4D6B5 BPBE BXBV CX B5

CNB4CPD7D7CTD6D8 CTDACTD2D8B4D6B5 BE BXBV CXA0BD CM CPD0DBCPDDD7CJ CTDACTD2D8CLB4D6B5 BPBE BV CX CM CPD7D7CTD6D8CJ CTDACTD2D8CLB4D6B5 BPBE BXBV CX B5CV.

On the basis of this compilation, we can define the belief set for a knowledge state CB:

Definition 6 Let CB and CD be as in Definition 5, and let CD BD BN BM BM BM BN CD D2 be the corresponding executable commands obtained from Definition 4. Then, the belief set of CB is given by BUCTD0B4CBB5 BP BUCTD0B4D8D6B4BUBN CD BD BN BM BM BM BN CD D2 B5B5BM

Example 3 Reconsider Example 2 and suppose the event BX BD BP CUD7CPD0CTB4D7 BC B5BN CSCPD8CTB4BDB5CV occurs at CB BP CWBUCX. Then,

BZB4CDB5 BD BP CUCPD7D7CTD6D8B4D7CPD0CTB4D7 BC B5B5 CXCU D2D3D8 CXCVD2D3D6CTB4D7CPD0CTB4D7 BC B5B5, CPD7D7CTD6D8B4CSCPD8CTB4BDB5B5 CXCU D2D3D8 CXCVD2D3D6CTB4CSCPD8CTB4BDB5B5, D6CTD8D6CPCRD8B4CSCPD8CT B4BCB5B5CVBM

The corresponding program A5 CD BD has the single answer set CUCPD7D7CTD6D8B4D7CPD0CTB4D7 BC B5B5BN CPD7D7CTD6D8B4CSCPD8CTB4BDB5B5BN D6CTD8D6CPCRD8B4CSCPD8CTB4BCB5B5CV, which is compiled, via function D8D6B4A1B5, to BV BD BP BV BC D2 CUCPD7D7CTD6D8 CJCTDACTD2D8CLB4CSCPD8CTB4BCB5B5CV BP BN and  BD BP CUD7CPD0CTB4D7 BC B5 AW D3D2B4D6 BC BD B5BN D3D2B4D6 BC BD B5 AW BN CSCPD8CTB4BDB5 AW D3D2B4D6 BC BE B5BN D3D2B4D6 BC BE B5 AW BN BMD3D2B4D6 BC B5 AW CV. As easily seen, the belief set BUCTD0B4CWBUBNBX BD CXB5 = BUCTD0B4B4 BC BN  BD B5B5 contains D7CPD0CTB4D7 BC B5 and D5D9CTD6DDB4D7 BC B5.

4 Properties

In this section, we discuss some properties of BUCTD0B4CBB5 for particular update policies, using the definition of BUCTD0B4A1B5 based on the update answer sets approach of Eiter et al. [2000], as explained in Section 2. We stress that the properties given below are also satisfied by similar instantiations of BUCTD0B4A1B5, like, e.g., dynamic logic programming [Alferes et al., 2000]. First, we note some basic properties:

• AF If CD BP BN (called empty policy), then BU will never be updated; the belief set is independent of BX BD BN BM BM BM BN BX D2 , and thus static. Hence, BUCTD0B4CB CX B5 BP BUCTD0B4BUB5, for each CX BP BDBN BM BM BM BN D2.
• AF If CD BP CUCPD7D7CTD6D8B4CAB5CJCJBX BMCACLCLCV (called unconditional assert policy), then all rules contained in the received events are directly incorporated into the update sequence. Thus, BUCTD0B4CB CX B5 BP BUCTD0B4B4BUBNBX BD BN BM BM BM BNBX CX B5B5, for each CX BP BDBN BM BM BM BN D2.
• AF If CD CX is empty, then the knowledge is not updated, i.e.,  CX BP BN. We thus have BUCTD0B4CB CX B5 BP BUCTD0B4CB CXA0BD B5.
• AF Similarly, if CD CX BP CUCPD7D7CTD6D8B4BR CX B5 AWCV, then BUCTD0B4CB CX B5 BP BUCTD0B4CB CXA0BD B5.

Physical removal of rules

An important issue is the growth of the agent's knowledge base, as the modular construction of the update sequence through transformation D8D6B4A1B5 causes some rules and facts to be repeatedly inserted. This is addressed next, where we discuss the physical removal of rules from the knowledge base.

Lemma 1 Let P BP B4 BC BN BM BM BM BN  D2 B5 be an update sequence. For every D6 BE  CX BN D6 BC BE  CY with CX BO CY, the following holds: if B4iB5 D6 BP D6 BC , or B4iiB5 D6 BP  AW and D6 BC BP BM AW , or B4iiiB5 D6 BC BP  AW such that no rule D6 BCBC BE  CZ with B4D6 BCBC B5 BP BM exists, where CZ BE CUCY B7 BDBN BM BM BM BN D2CV, and BM BE BUB4D6B5, then BUCTD0 BT B4PB5 BP BUCTD0 BT B4 BC BN BM BM BM BN  CXA0BD BN  CX D2 CUD6CVBN  CXB7BD BN BM BM BM BN  D2 B5BM

The following property holds:

Theorem 1 Let CB be a knowledge state and BUCTD0B4CBB5 BP BUCTD0B4PB5, where P BP B4 BC BN BM BM BM BN  D2 B5. Furthermore, let P A3 result from P after repeatedly removing rules as in Lemma 1, and let P A0 BP B4 A0 BC BN BM BM BM BN  A0 D2 B5, where

Thus, we can purge the knowledge base and remove duplicates of rules, as well as all deactivated (retracted) rules.

History Contraction

Another relevant issue is the possibility, for some special case, to contract the agent's update history, and compute its belief set at step CX merely based on information at step CXA0BD. Let us call CD a factual assert policy if all assert[ event] and always[ event] statements in CD involve only facts. In this case, the compilation D8D6B4A1B5 for a knowledge state CB BP CWBUBNBX BD BN BM BM BM BNBX D2 CX can be simplified thus: (1)  BC BP BU, and (2) the construction of each  CX involves facts  AW and BM AW instead of D3D2B4D2 D6 B5 AW and BMD3D2B4D2 D6 B5 AW , respectively. For such sequences, the following holds:

Lemma 2 Let P BP B4 BC BN BM BM BM BN  D2 B5 be an update sequence such that  CX contains only facts, for BD AK CX AK D2. Then, BUCTD0 BT B4PB5 BP BUCTD0 BT B4 BC BN  D9 D2 B5, where  D9 BD BP  BD , and  D9 CXB7BD BP  CXB7BD CJB4 D9 CX D2 CU AW CY BM AW BE  CXB7BD CVB5.

We can thus assert the following proposition for history contraction:

Theorem 2 Let CD be a factual assert policy and P BP B4 BD BN BM BM BM BN  D2 B5 be the compiled sequence obtained from CB by the simplified method described above. Then, BUCTD0 BT B4CBB5 BP BUCTD0 BT B4B4BUBN  D9 D2 B5B5, where  D9 D2 is as in Lemma 2.

Simple examples show that Theorem 2 does not hold in general. The investigation of classes of policies for which similar results hold are a subject for further research.

Computational Complexity

Finally, we briefly address the complexity of reasoning about a knowledge state CB . An update policy CD is called stratified iff, for all BX
statements CRD1CSB4AQB5 CXCU BV BD CJCJBV BE CLCL BE CD, the associated rules CRD1CS BD B4AQB5 AW BV BC BD form a stratified logic program, where BV BC BD results from BV BD by replacing the BX
declaration D2D3D8 by default negation D2D3D8 .

For stratified CD, any A5 CD CX has at most one answer set. Thus, the selection function CBCTD0B4A1B5 is redundant. Otherwise, the complexity cost of CBCTD0B4A1B5 must be taken into account. If CBCTD0B4A1B5 is unknown, we consider all possible return values (i.e., all answer sets of A5 CD CX ) and thus, in a cautious reasoning mode, all possible BUCTD0B4CBB5 BP BUCTD0B4B4 BC BN BM BM BM BN  D2 B5B5 from Figure 1. Clearly, for update answer sets, deciding D6 BC BE BUCTD0B4B4 BC BN BM BM BM BN D1 B5B5 is in coNP; it is polynomial, if BC is stratified and each CX , BD AK CX AKD1, contains only facts.

Theorem 3 Let BUCTD0B4A1B5 be the update answer set semantics, and CBCTD0B4A1B5 polynomial-time computable with an NP oracle. Then, given a ground rule D6 and ground CB BP CWBUBNBX BD BN BM BM BM BNBX D2 CX, the complexity of deciding whether D6 BE

Similar results hold, e.g., for dynamic logic programming. The results can be intuitively explained as follows. Each CD CX and  CX as in Figure 1 can be computed iteratively (BD AK CX AK D2), where at step CX polynomially many problems D6 BC BE BUCTD0B4B4 BC BN BM BM BM BN  CXA0BD B5B5 must be solved to construct A5 CD CX . From CD CX BP CBCTD0B4A5 CD CX B5 and previous results,  CX is easily computed in polynomial time. Since  CX contains less than CYCDCY rules, step CX is feasible in polynomial time with an NP oracle. Thus, P BP B4 BC BN BM BM BM BN  D2 B5 is polynomially computable with an NP oracle, and D6 BE BUCTD0B4PB5 is decided with another oracle call. Updating a stratified  BC such that only sets of facts  BD ,  BE BN BM BM BM may be added preserves polynomial decidability of D6 BC BE BUCTD0B4B4 BC BN BM BM BM BN  CXA0BD B5B5; this explains the polynomial decidability result. In all other cases,   -hard problems such as computing the lexicographically maximal model of a CNF formula are easily reduced to the problem.

If CBCTD0B4A1B5 is unknown, each possible result of CBCTD0B4A5 CD CX B5 can be nondeterministically guessed and verified in polynomial time. This leads to coNP  BP A5  BE complexity.

5 Implementational Issues

An elegant and straightforward realization of update policies is possible through IMPACT agent programs. IMPACT [Subrahmanian et al., 2000] is a platform for developing software agents, which allows to build agents on top of legacy code, i.e., existing software packages, that operates on arbitrary data structures. Thus, in accordance with our approach, we can design a generic implementation of our framework, without committing ourselves to a particular update semantics BUCTD0B4A1B5.

Since every update policy CD is semantically reduced to a logic program, the corresponding executable commands can be computed using well-known logic programming engines like D7D1D3CSCTD0D7, BWCE, or BWCTCACTD7. Hence, we may assume that a software package, CB, for updating and querying a knowledge base BU is available, and that BU can be accessed through a function CQCTD0B4B5 returning the current belief set BUCTD0B4CBB5. Moreover, we assume that CB has a function CTDACTD2D8B4B5, which lists all rules of a current event. Then, an update policy CD can be represented in IMPACT as follows.

(1) Conditions on the belief set and the event can be modeled by IMPACT code call atoms, i.e. atoms CXD2B4D8BN CQCTD0B4B5B5, D2D3D8 CXD2B4D8BN CQCTD0B4B5B5, and CXD2B4D8BN CTDACTD2D8B4B5B5, where D8 is a constant D6 or a variable CA. In IMPACT, CXD2B4D6BN CUB4B5B5 is true if constant D6 is in the result returned by CUB4B5; a variable CA is bound to all D6 such that CXD2B4D6BN CUB4B5B5 is true; "D2D3D8 CXD2" is negation.

(2) Update commands can be easily represented as IMPACT actions. An action is implemented by a body of code in any programming language (e.g., C); its effects are specified in terms of add and delete lists (sets of code call atoms). Thus, actions like CPD7D7CTD6D8B4CAB5, D6CTD8D6CPCRD8B4CAB5, etc., where CA is a parameter, are introduced.

(3) BX
statements are represented as IMPACT action rules

BWD3B4CRD1CS BD B4AQ BD B5B5 AW CJBMCLBWD3B4CRD1CS BE B4AQ BC B5B5BN BM BM BM BN CJBMCLBWD3B4CRD1CS D1 B4AQ BC B5B5BN CRD3CSCT CRCPD0D0 CPD8D3D1D7B4CRD3D2CSB5BN

where CRD3CSCT CRCPD0D0 CPD8D3D1D7B4CRD3D2CSB5 is the list of the code call atoms for the conditions on the belief set and the event in CRD3D2CS as described above.

The semantics of IMPACT agent programs is defined through status sets. A reasonable status set CB is equivalent to a stable model of a logic program, and prescribes the agent to perform all actions AB where BWD3B4ABB5 is in CB. Thus, CB represents the executable commands CD CX of Figure 1 in accord with CD, and the respective action execution affects the computation of  CX via D8D6B4A1B5. For more details, cf. [Eiter et al., 2001].

6 RelatedWork and Conclusion

Our approach is similar in spirit to the work in active databases (ADBs), where the dynamics of a database is specified through event-condition-action (ECA) rules triggered by events. However, ADBs have in general no declarative semantics, and only one rule at a time fires, possibly causing successive events. In [Baral and Lobo, 1996], a declarative characterization of ADBs is given, in terms of a reduction to logic programs, by using situation calculus notation.

Our language for update policies is also related to action languages, which can be compiled to logic programs as well (cf., e.g., [Lifschitz and Turner, 1999]). A change to the knowledge base may be considered as an action, where the execution of actions may depend on other actions and conditions. However, action languages are tailored for planning and reasoning about actions, rather than reactive behavior specification; events would have to be emulated. Furthermore, a state is, essentially, a set of literals rather than a belief set as we define it. Investigating the relationships of our framework to these languages in detail-in particular concerning embeddings-is an interesting issue for further research.

A development in the area of action languages, with purposes similar to those of BX
, is the policy description language BW [Lobo et al., 1999]. It extends traditional action languages with the notion of event sequences, and serves for specifying actions as reactive behavior in response to events. A BW policy is a collection of ECA rules, interpreted as a function associating with an event sequence a set of actions. BW seems thus to be more expressive than BX
; possible embeddings of BX
into BW remain to be explored.

The BX
language could be extended with several features:

1. Special atoms CXD2B4D6B5 telling whether D6 is actually part of BU (i.e., activated by D3D2B4D2 D6 B5), allowing to access the "extensional" part of BU.
2. Rule terms involving literal constants and variables, e.g., " AW D9D4B4D7 BD B5BN BU", where BN BU are variables and D9D4B4D7 BD B5 is a fixed atom, providing access to the structure of rules. Combined with (1), commands such as "remove all rules involving D9D4B4D7 BD B5" can thus be conveniently expressed.
3. More expressive conditions on the knowledge base are conceivable, requesting for more complex reasoning tasks, and possibly taking the temporal evolution into account. E.g., "D4D6CTDAB4CPB5" expressing that CP was true at the previous stage.

In concluding, our generic framework, which extends other approaches to logic program updates, represents a convenient platform for declarative update specifications and could also be fruitfully used in several applications. Exploring these issues is part of our ongoing research.

Acknowledgements

This work was partially supported by the Austrian Science Fund (FWF) under grants P13871-INF and N Z29-INF.