Revising and updating beliefs and knowledge bases is an important topic in knowledge representation and reasoning that requires a solid theoretical basis. As a result, various researchers have proposed Answer Set Programming as one of their key components to set up their approaches. In the need to satisfy more general principles, this paper presents a new characterisation of a semantics. It consists in performing updates of epistemic states that meets well-accepted AGM revision postulates. Besides the formalism of properties that this framework shares with other equivalent update semantics, this proposal is also supported by a solver prototype as an important component of logic programming and automatic testbed of its declarative version. The solver may help compute agent's knowledge bases for more complex potentially-industrial applications and frameworks.
One of the latest proposals to meet most well-accepted principles for updates
at the object level and in Minimal Generalised Answer Sets (MGAS) was rst
introduced in [
A deep analysis of the problem, the solution, justi cation, basic model-oriented
properties and comparison with other approaches are available in [
The semantics is formally expressed with the following set of de nitions,
borrowed and slightly modi ed from [
Formally, an -relaxed rule is a rule that is weakened by a default-negated atom in its body: Head( ) Body( ) [ fnot g. In addition, an -relaxed program is a set of -relaxed rules. ? This project is supported by a CONACYT Doctorate Grant.
A generalised program is a set of rules of form ` > j ` 2 A , where A is a given set of literals.
As a consequence, updating a program with another consists in transforming an ordered pair of programs into a single abductive program, as follows. De nition 1 ( o-update Program). Given an updating pair of extended logic programs, denoted as 1 o 2, over a set of atoms A; and a set of unique abducibles A , such that A \ A = ;; and the abductive program A = h 0 [ 2; A i with its corresponding -relaxed program 0 such that 2 A , and its corresponding MGAS's. Its o-update program is 0 [ 2 [ G, where G is a generalised program of M \ A for some MGAS M of A and o is the corresponding update operator.
Last, the associated models S of an epistemic state (an updating pair) corresponds to the answer sets of a o-update program as follows.
De nition 2 ( o-update Answer Set). Let o = ( 1 o 2) be an update pair over a set of atoms A. Then, S A is an o-update answer set of o if and only if S = S0 \ A for some answer set S0 of its o-update program. 3
o-Properties The properties of this simple formulation are the main result of this current semantics for successive updates of epistemic states. 3.1
o-Principles
One of the contributions of this paper is a particular interpretation and
characterisation of AGM [
My own interpretation of postulates (R 1){(R 6) corresponds to postulates (RG 1){(RG 6) below: (RG (RG (RG (RG (RG (RG 1) 1 2) If 3) If 4) If 5) 6) If (
1. [ 1 is consistent, then 1 is consistent, then 1 N2 2 then 1 ( 1 [ 2) ( 1) [ 2.
1) [ 2 is consistent, then (
1 [ 1. 1 is also consistent.
2.
1) [
2
( 1 [
2).
where being consistent means having answer sets; \ " is a generic revision
operator ; and \ 1 2" means that 1 and 2 have the same answer sets. Last,
\ 1 N2 2" means that the corresponding translated programs 1 and 2
into N2 Nelson's logic theories are equivalent [
As an interesting result, let us consider (RG 3) in order to formulate the following lemma, from which one can get a more general property.
Lemma 1 (weak consistency view). Suppose 0 and 1 are ELP's and an updating pair 0 o 1 with its corresponding abductive program A = h 0 [ 1; A i. If 1 is consistent then A is consistent.
Corollary 1 (consistency recovery). Suppose update 0 o 1 is consistent if 1 is consistent. 0 and 1 are ELP's. The
Corollary 1 also proves to be useful satisfying belief revision postulates. Theorem 1 (RG -properties). Suppose that operator \ o" satis es properties (RG 1){(RG , 1 and 4) and (RG 2 are ELP. Update 6).
Nevertheless, postulate (RG 5) does not hold. As a counterexample, consider the following programs: = fa >; :b >; :c >g; 1 = fb >g; 2 = fc >g. This counterexample inverts the direction of the relation. 4
Conclusions This paper presents work in progress of a generalisation of o-operator that satis es ve of the six most suitable belief-revision postulates for updating epistemic states. As a result, this framework provides a strong theoretical foundation on well-known principles and other fundamental properties.
Finally, as a classical component of Logic Programming, this operator has an implemented solver prototype at http://www2.in.tu-clausthal.de/~guadarrama/ updates/o.html, as an automatic testbed that makes the semantics more accessible (in a classroom, i.e.), and potential component for further more complex prototypes in administration of (toy?) knowledge systems, with precise properties. Further details, examples and proofs are coming up in an extended version.