=Paper= {{Paper |id=Vol-1423/paper4 |storemode=property |title=Arbitrary Announcements in Propositional Belief Revision |pdfUrl=https://ceur-ws.org/Vol-1423/DARe-15_4.pdf |volume=Vol-1423 |dblpUrl=https://dblp.org/rec/conf/ijcai/HunterS15 }} ==Arbitrary Announcements in Propositional Belief Revision== https://ceur-ws.org/Vol-1423/DARe-15_4.pdf

Arbitrary Announcements in Propositional Belief Revision

Aaron Hunter Francois Schwarzentruber
British Columbia Institute of Technology ENS Rennes
Burnaby, Canada Bruz, France
aaron hunter@bcit.ca francois.schwarzentruber@ens-rennes.fr

Abstract
V
consistent, so announcing i ψi is not a solution in all cases.
The problem that we address roughly corresponds to the no-
Public announcements cause each agent in a group tion of an arbitrary public announcement [BBvD+ 07] in the
to modify their beliefs to incorporate some new tradition of Dynamic Epistemic Logic (DEL) [vDvdHK08],
piece of information, while simultaneously being except that we do not require announcements to be truthful.
aware that all other agents are doing the same. However, the problem is far simpler computationally in the
Given some fixed goal formula, it is natural to ask setting of propositional revision. As such, we suggest that
if there exists an announcement that will make the our approach is appropriate for practical applications, such as
formula true in a multi-agent context. This problem robot controllers, where the focus is on giving factual orders
is known to be undecidable in a general modal set- in the most efficient way possible.
ting, where the presence of nested beliefs can lead This paper makes several contributions to existing work on
to complex dynamics. In this paper, we consider the theory of belief change. First, we define arbitrary pub-
not necessarily truthful public announcements in lic announcements in an AGM setting. We demonstrate that
the setting of propositional belief revision. We are the question is meaningful in this context, as there are natural
given a goal formula for each agent, and we are in- applications where a reasonable treatment of announcements
terested in finding a single announcement that will need not be concerned with nested beliefs. A non-trivial sec-
make each agent believe the corresponding goal ond contribution of the paper is a detailed analysis of the com-
following AGM-style belief revision. If the goals plexity of arbitrary announcements for a particular AGM re-
are inconsistent, then this can be seen as a form of vision operator, namely Dalal’s revision operator [Dal88]. Fi-
ampliative reasoning. We prove that determining nally, from a high-level perspective, this paper makes a con-
if there is an arbitrary public announcement in this tribution towards establishing the utility of AGM-style oper-
setting is not only decidable, but that it is simpler ators with respect to the (more expressive) DEL approach to
than the corresponding problem in the most simpli- belief change.
fied modal logics. Moreover, we argue that propo- We do not define arbitrary public announcements for a full
sitional announcements and beliefs are sufficient Dynamic epistemic logic for belief revision ([VB07], [BS06],
for modelling many practical problems, including [BS08]) because it would certainly lead to undecidability is-
simple robot controllers. sues [FvD08]. We concentrate here on the propositional case:
announcements are propositional and we are only interested
1 Introduction in propositional beliefs. Many natural reasoning problems
can be captured in this setting, including the motivating ex-
We are concerned with the manner in which the beliefs of ample below. We are interested in computational issues in
a group of agents can be manipulated by making group this context.
announcements. Following the highly influential work of
[BMS98], this issue has been studied extensively in modal
logics of public announcement. We are interested in the Motivating Example Consider a domain involving a robot
propositional case involving belief revision operators. As controller, and n robots that act independently. Each robot
such, we assume that each agent i has some initial belief set has beliefs about the current state of the world, and these be-
Ki and as well as a goal formula ψi . We would like to find liefs are used to formulate goals. We assume that the goals
a single consistent formula φ that can be announced to all are given as input to some form of planner, but we are not
agents such that Ki ∗ φ |= ψi for all i, where ∗ represents concerned with reasoning about actions here. Assume that
some suitable model of AGM-style belief 1 the only way the controller can communicate with the robots
V revision . Note is through broadcast messaging. If there are constraints on
that the conjunction of the goal formulas i ψi need not to be
messaging in terms of cost or timing, then the controller may
1 seek to minimize the number of messages sent to ensure all
AGM stands for the highly influential approach to belief revi-
sion due to Alchourròn, Gärdenfors and Makinson [AGM85]. robots have the correct goals. Towards this end, it can be use-
ful to send messages that will impact the beliefs of each robot M = hW, R1 , . . . , Rn , V i where W is a non-empty set of
differently. possible worlds, each Ri is a binary accessibility relation on
As a concrete example, suppose that there are two surveil- W , and V is a function that assigns an interpretation to each
lance robots R1 and R2 that are tasked with patrolling a cer- w ∈ W . Formulas in modal logic can take the form i φ;
tain area. If there is a breach at the gate, we would like and we have M, w |= i φ just in case (M, v) |= φ for every
one robot to go check the gate while the other continues v with (w, v) ∈ Ri . Standard modalities include K (knowl-
patrolling. In order to achieve the desired behaviour, the edge), B (belief), and the parametrized public announcement
controller would like to broadcast a single alarm message modality [φ] of dynamic epistemic logic. The semantics of [φ]
“breach” that will lead each robot to simultaneously have the is defined as a restriction to possible worlds where φ holds.
appropriate beliefs about how they should behave. In this pa- We refer the reader to [vDvdHK08] for a survey of work in
per, we formalize this kind of reasoning in an abstract setting. this area.
One important distinction between the AGM approach and
2 Preliminaries the DEL approach is the fact that the DEL approach permits
the representation of nested beliefs. As a result, it is much
2.1 Belief Revision more expressive. Also, some of the properties we expect for
A vocabulary is a countable set of propositional variables P. belief change no longer hold. For example, consider the Suc-
An interpretation over P is a function that maps each vari- cess postulate for AGM revision, which states that φ ∈ K ∗ φ.
able to a truth value, and assigns truth values to propositional In a modal setting, this is essentially equivalent to the schema
formulas in the usual way. The study of belief change is con- [φ]Bφ. This is not valid in most multi-agent epistemic logics,
cerned with the way that rational agents incorporate new in- because an announcement of φ often changes the world such
formation. One important form of belief change is belief re- that φ should not actually be believed.2 .
vision, which is the change that occurs when the new infor- This leads to a natural question: how can we get an-
mation may be inconsistent with some of the original beliefs. other agent to believe some formula φ? This question is ad-
One highly influential approach to belief revision has been dressed in DEL via the logic of arbitrary public announce-
the AGM approach, in which belief revision is captured by ments [BBvD+ 07]. Note that the problem is not identical,
an operator that satisfies a particular set of rationality postu- however, to the problem addressed in this paper. First of
lates [AGM85]. In this tradition, the beliefs of an agent are all, we do not have belief revision operators in public an-
represented by a belief set, which is a logically closed set of nouncement logic; we have only hard updates. Furthermore,
formulas; if we have a finite vocabulary, this can equivalently in DEL we require announcements to be truthful. In arbi-
be a single formula. A belief revision operator takes a belief trary public announcement logic, through a modality ♦ such
set and a formula as input, and returns a new belief set. that ♦φ is true just in case there is some truthful formula ψ
It is well-known that every AGM revision operator ∗ has such that announcing ψ would make φ true. If φ has the form
the property that, for any belief set K, there is an underlying B1 φ1 ∧ · · · ∧ Bn φn , then we have a DEL reformulation of
total pre-order ≺K such that K ∗ φ = min≺K (φ); so AGM the variant of the problem that we address in this paper, mod-
revision involves finding minimal worlds consistent with a ulo hard updates and truth of announcements. We invite the
particular formula [KM92]. One problem with the AGM ap- reader to refer to [vDvdHK04] for a precise comparison be-
proach is that, in general, it does not handle the problem of tween public announcement and belief revision.
iterated belief revision. The problem is that you have an or-
dering on states before the revision, but you only have a set 2.3 Dynamic epistemic logic with plausibility
of states after the revision. models
Iterated revision requires a specification of exactly how the
A version of DEL has been defined to incorporate belief re-
ordering changes when presented with a formula for revision
[DP97; JT07]. As such, iterated belief revision operators are vision operators ([VB07], [BS06], [BS08]). In this logic,
the epistemic relations for belief operators do not rely on
commonly defined in terms of epistemic states. An epistemic
fixed (traditionally KD45) relations on possible worlds. In-
state is a total pre-order ≺ over the set of states. A belief
stead, for each agent a, possible worlds are ordered in each
change operator ∗ takes a total pre-order ≺ and a formula φ
equivalence class for a. The semantics of [φ] is defined in
as input, and it returns a new epistemic state denoted ≺ ∗ φ.
terms of model transformations that re-order the orderings
The set min(≺) is understood to represent the set of states
over worlds. As far we know, arbitrary public announcements
that are currently believed by a given agent. A DP (Darwiche
have never been considered in this context.
and Pearl) revision operator satisfies the postulates introduced
in [DP97]. The key distinction here is that DP revision is con-
2.4 Complexity Results
cerned with returning a completely new ordering following
revision, so we are able to revise again if necessary. In this section, we give some known complexity results re-
lated to public announcements. The first result is really the
2.2 Dynamic Epistemic Logic starting point for this work.
An alternative approach to reasoning about beliefs has Theorem 1 ([FvD08]) Satisfiability in the logic of arbitrary
been developed using variations of Dynamic epistemic logic announcements is undecidable.
[vDvdHK08]. The semantics of these logics is defined with
2
respect to Kripke structures. A Kripke structure is a tuple This is the case in so-called Moore sentences, for example.
Hence, if we have nested knowledge and a rich domain of robot should be patrolling their area and the checkgate vari-
Kripke structures, we can not hope to find public announce- able is true when the robot is supposed to check the gate.
ments to change the beliefs of agents in the desired man- Suppose we have two robots R1 and R2 with initial belief
ner. A simpler logic called DLPA-APAL (for dynamic logic states defined as follows:
of propositional assignments with arbitrary public announce-
Bel(R1 ) = {¬patrol ∨ checkgate}
ment logic) is defined in [CS15]. In DLPA-APAL, Kripke
structures are restricted to include just one world with each Bel(R2 ) = {¬patrol ∨ ¬checkgate}
valuation, and epistemic relations are represented by pro- The controller believes there is a problem at the gate. Is there
grams over propositional assignments. a formula that can be broadcast to immediately get R1 to
Theorem 2 ([CS15]) Satisfiability in DLPA-APAL is check the gate while R2 patrols the the grounds? In other
NEXPTIME-complete for the single announcement case. words, is there a formula φ such that:
This result shows that restricting to reasoning over beliefs on {¬patrol ∨ checkgate} ∗ φ |= checkgate
valuations is decidable. Our goal in this paper is to show that {¬patrol ∨ ¬checkgate} ∗ φ |= ¬checkgate ∧ patrol
if we restrict further, by removing nested beliefs, we can get
The answer here is clearly yes because we can set
a better complexity even if we use belief revision operators
φ = patrol.
and we do not force announcements to be true.
The preceding example is framed in the context of the
3 Propositional Effects of Announcements robot controller, but it also demonstrates an important case
3.1 The Basic Problem for propositional announcement. In particular, it shows that
there are cases where the goals are inconsistent, yet a solution
Given n agents and an AGM revision operator ∗, we are look- is possible. We are interested in determining how difficult it
ing for the existence of a consistent formula φ such that is to find such a solution.
K1 ∗ φ |= ψ1 (1) 3.2 Decision problem
K2 ∗ φ |= ψ2 In this section, we give an algorithm to solve the problem
.. of interest. But, let us consider the corresponding decision
. problem.
Kn ∗ φ |= ψn
The Propositional Announcement Problem (PAP(∗))
where Ki and ψi represent the belief Input:
Vset and the goal of the
agent i, respectively. Obviously, if i ψi is consistent, then An integer n
we can just revise by this. But this is not always the case. A list K1 , . . . , Kn of formulas (initial beliefs).
Note that we do not require the announcement to be true A list ψ1 , . . . , ψn of formulas (goals).
as it is done in public announcement logic. We remark also Ouput:
that, in a propositional setting, there is no way to express an Yes, if there exists φ satisfying (1)
assertion of the form “if you are agent i, then revise by φ.” No, otherwise.
As such, there is no obvious way to specify a formula that
explictly specifies a different revision for each agent. We refer to this problem as P AP (∗) to emphasize that it de-
As formulated above, the announcement problem can be pends on some given operator ∗ on belief sets. In this paper,
seen as V a form of distributed ampliative reasoning. In gen- we will assume ∗ is an AGM revision operator, but that need
eral, if i ψi is not consistent, then it is not possible to find not be the case in general.
a consistent formula to announce that will result in a single We may reformulate P AP (∗) in a variant of the model
agent believing each ψi . But in our setting, we are actu- checking problem of Dynamic epistemic logic with plausi-
ally able to get some agent to believe each ψi . Hence, the bility models ([VB07], [BS06]). We create a (potentially ex-
announcement of φ is resulting in a situation where the dis- ponentially bigger than K1 , . . . , Kn ) pointed Kripke model
tributed beliefs of the agents in the system are inconsistent; M, w such that the valuations of the most plausible worlds
since the formula φ itself is consistent, this means that some in w are exactly models of Ki for all agents i ∈ {1, . . . , n}.
of the revising agents are “jumping to conclusions” that are Then we ask whether there exists a propositional formula φ
not strictly supported by the announcement. such that M, w |= [φ]BR (B1 ψ1 , . . . , Bn ψn ) where [φ]BR is
the announcement operator that semantically performs the be-
Example Consider the robot controller example over the lief revision for all agents and Bi is the belief operator for
vocabulary {patrol, checkgate}. We think of this vocabulary agent i.
as defining a state machine, where each interpretation repre- For the moment, we are interested in analyzing the simplest
sents a state; the robot can have actions that are triggered by case to obtain the most efficient algorithm possible. Hence,
transitions to given states. This is a standard control mech- we consider Dalal’s revision operator based on the Ham-
anism for simple agents in a video game setting, and it can ming distance between interpretations [Dal88], which also
function as a control mechanism for our simple robot agents has the advantage that it allows iterated revision. Let ∗d be
as well. In our example, the patrol variable is true when the the Dalal’s revision operator.
We present a non-deterministic algorithm that decides in the complexity class ΣP2 = NP
NP
. The following result
P AP (∗d ). In the algorithm, we use non-determistic choice makes this claim precise.
to select the minimum distance di between Ki and ψi . Also
note that d(K, v) denotes the minimum Hamming distance Theorem 4 PAP(∗d ) is in ΣP
2.
between the set of interpretations representing by formula K Proof After the initial guesses, the algorithm clearly
and interpretation v. runs in polynomial time other than the checks of the form
FIND ANN (K1 , . . . , Kn , ψ1 , . . . , ψn ) d(K, v) < d at several stages. But recall that we are using
0. Let m be the size of the underlying input vocabulary of the Hamming distance here, so this check can be performed
K1 , . . . , Kn , ψ1 , . . . , ψn as follows. Guess a set of atomic propositional variables of
1. Guess d1 , . . . , dn ∈ {0, 1, . . . , m} size less than d, and let v 0 be the interpretation obtained from
2. Guess valuations v1 , . . . , vn v by switching the truth values of these variables. If v 0 |= K,
3. For all i, j ∈ {1, . . . , n} then the minimum distance between K and v is less than d.
If d(Kj , vi ) < dj , reject. This process is in N P .
4. For all i ∈ {1, . . . , n} Hence the entire algorithm runs in time N P with a poly-
If d(Ki , vi ) > di , reject. nomial number of calls to an N P oracle. This gives the com-
5. For all i, j ∈ {1, . . . , n} plexity N P N P = ΣP 2 , which was the desired result.
If d(Kj , vi ) = dj and vi 6|= ψj , reject.
6. Accept. Thus, finding an announcement is far much efficient than
in the modal case, even if we restrict possible worlds to be
We need to prove that FIND ANN(K̄, ψ̄) actually produces valuations. Note that hardness of PAP(∗d ) is left as an open
the desired result. In the proof, we write min≤Ki (φ) for the issue.
minimal Hamming distance from a model of φ to a model of So far, we have restricted attention to Dalal’s revision op-
Ki . erator. The primary motivation for this choice is the fact that
Theorem 3 Let K̄ = K1 , . . . , Kn and let ψ̄ = ψ1 , . . . , ψn Dalal’s operator permits iterated revision, which we antici-
be sequences of formulas. Then FIND ANN(K̄, ψ̄) accepts pate will be important in practice for a robot controller. In-
if and only if there exists φ such that Ki ∗d φ |= ψi for each i. spection of our proofs shows that the actual properties of the
Hamming distance operator only occur in two places.
Proof Suppose that FIND S ANN(K̄, ψ̄) accepts. Let φ be
a formula with ||φ|| = i {vi }, where the valuations vi are • When the minimum distance is guessed in the algorithm.
those from an accepting run chosen on lines 1 and 2. By
• In a number of checks of the form d(K, v) < d.
line 3,
min(φ) ≥ dj In these cases, we are able to have a polynomial number of
≤Ki operations with the Dalal’s revision operator, because the dis-
because if this is not the case, the valuations would have been tance only ranges from 0 to the size of the vocabulary. How-
rejected. But then, by line 4, ever, this is obviously not true for other revision operators;
we return to this point in the conclusion.
min(φ) = dj .
≤Ki

In other words, for each i, the models of φ that are models 4 Existence of Solutions
of Ki are distance di from Ki . Finally, since line 5 also is In this section, we give some basic results related to the exis-
false for an accepting run, it follows that for every v such tence of solutions for the propositional announcement prob-
that v |= φ, it must be the case that d(Kj , v) = dj implies lem. Note that the problem we have considered thus far as-
v |= ψj . Hence, the minimal models of φ with respect to Ki sumes a single AGM revision operator that is used by all
are also models of ψi . So K ∗ φ |= ψi , which is what we agents. This is, of course, not the most general setting. A
wanted to show. more general version of our problem takes n agents and n be-
Now suppose that there exists φ such that Ki ∗d φ |= ψi for lief revision operators ∗i as input; we are still looking for the
each i. For each i, define di = min≤Ki (φ). For each i, let vi existence of a consistent formula φ such that
denote one of the valuations of ψi such that d(Ki , vi ) = di .
We know that such a vi exists, since Ki ∗d φ |= ψi . If we K1 ∗1 φ |= ψ1 (2)
use d¯ = d1 , . . . , dn and v̄ = v1 , . . . , vn on lines 1 and 2 K2 ∗2 φ |= ψ2
of the algorithm, then the choice of these values leads to an ..
accepting run. .
Kn ∗n φ |= ψn
So FIND ANN(K̄, ψ̄) does what we want it to do: it deter-
mines if there is a public announcement φ such that revision where Ki and ψi represent the belief set and the goal of the
by φ for each agent satisfies all ψi . We can also say something agent i, respectively. Note that this is a slightly more general
about the complexity. The initial guessing is a polynomial problem than the problem we addressed previously; we will
number of guesses with respect to the input length. Note that state our results in this section with respect to this formulation
in the algorithm, tests d(Kj , vi ) < dj etc. can be answered of the announcement problem.
by an NP oracle. Hence, the algorithm intuitively seems to lie The following result is immediate.
Theorem 5 For all n > 1, there are instances of (2) with no
solution.
Proof Assume the vocabulary {p}, let K1 = {p},
K2 = {¬p}, ψ1 = ¬p and ψ2 = p. It follows immedi-
ately that any solution φ satisfies φ |= p ∧ ¬p, so there is no
consistent solution.

The following result may be less obvious, but it is similarly
straightforward. The idea is simply that, as long as there are
“enough” propositional variables, we can set up a set of in-
consistent goals that can be guaranteed by an appropriate re-
vision.
Theorem 6 Let n be a fixed natural number, and let P be
a propositional vocabulary. If |P| > log2 n, then there is
an instance of (2) over P with inconsistent goals that has a
solution.
Proof Assume the instance size n is given. Let P0 , . . . , Pn
be a list of mutually inconsistent maximal conjunctions over
literals of P; we know that such a list exists, because there are
2|P| distinct maximal conjunctions of literals, and we know
that 2|P| > n by assumption. For each i, we set:
^
Ki = (¬P0 ∨ Pi ) ∧ ¬Pj
j6=i
^
ψi = Pi ∧ ¬Pj
j6=i
V
Note that the conjunction i ψi is clearly inconsistent. If we
set φ = P0 , then it is easy to verify that Ki ∗i φ |= ψi for
each i, which is what we wanted to show.

These results demonstrate that the general propositional an-
nouncement problem is non-trivial. There are instances with
no solution and there are instances with solutions, and we can
not easily identify which is the case without considering the
possible revisions.

5 Prototype Development
As noted previously, we are interested in using propositional Figure 1: Demo Interface
announcements in a practical implementation of a robot con-
troller. Unfortunately, the algorithm provided in this paper is
for a decision problem, so it does not actually return the an-
nouncement. However, it is easy to modify the algorithm to
return the induced formula φ.
has calculated an announcement that will achieve this goal.
We have developed a simple implementation that calcu-
The announcement is computed with the algorithm presented
lates the formula suggested by our algorithm, and performs
in subsection 3.2 except that guesses are replaced by explicit
revision by the given announcement in the two agent case. In
loops.
the demo, a number of variables are introduced to represent
different weather conditions. Notably, there is a variable b
indicating that an agent believes there is a rainbow and there We remark that, in most cases, the formula generated by
is a variable c indicating that it is cloudy. A screenshot is our prototype implementation is very large and difficult to
provided in Figure 1. Suppose that initially agent 1 believes work with; it is really just a disjunction of maximal con-
c → ¬b and agent 2 believes c → b (in the software, we junctions describing all the suitable interpretations. In future
may reach this situation by announcing privately c → ¬b to work, we intend to improve the implementation to return a
agent 1 and announcing privately c → b to agent 2). In the smaller formula. This could be done as a post-processing step
Figure, we would like agent 1 to believe c and ¬b whereas following the calculation currently performed, or it could be
we would like agent 2 to believe both c and b. The software done through the development of a new search algorithm.
6 Discussion [BMS98] A. Baltag, L. Moss, and S. Solecki. The logic
6.1 Future Work of public announcements, common knowledge
and private suspicions. In Proceedings of the
In this paper, we have only addressed the complexity of arbi- Conference on Theoretical Aspects of Ratio-
trary public announcement in the case of the Dalal’s revision nality and Knowledge (TARK-98), pages 43–
operator, where the the number of levels in the plausibility 56, 1998.
ordering is at most |P| (the size of the vocabulary). In gen-
eral, the worst case complexity to check all levels of a total [BS06] Alexandru Baltag and Sonja Smets. Dynamic
pre-order over a vocabulary of size P will be 2|P| . If we are belief revision over multi-agent plausibility
actually required to make this many checks, then the deci- models. In Proceedings of LOFT, volume 6,
sion problem for other revision operators would lie at a higher pages 11–24, 2006.
level of the polynomial hierarchy. This would not necessar- [BS08] Alexandru Baltag and Sonja Smets. A qualita-
ily be surprising, as it would follow the same pattern seen in tive theory of dynamic interactive belief revi-
Eiter and Gottlob’s classic paper on the complexity of vari- sion. Texts in logic and games, 3:9–58, 2008.
ous revision operators [EG92]. We do not know at this point [CS15] T. Charrier and F. Schwarzentruber. Arbitrary
if we actually need to check all possible levels in the underly- public announcement logic with mental pro-
ing plausibility ordering for this particular application; it may grams. In Proceedings of the 2015 Interna-
be the case that we can perform fewer checks when the or- tional Conference on Autonomous Agents and
dering is defined by an AGM revision operator. We leave the Multi-Agent Systems, 2015.
complexity of other AGM revision operators for future work.
It would also be useful to consider the announcement prob- [Dal88] M. Dalal. Investigations into a theory of
lem for iterated revision. In this context, the problem takes n knowledge base revision. In Proceedings of the
agents and n DP revision operators ∗i as input. We are look- National Conference on Artificial Intelligence
ing for the existence of a consistent formula φ such that (AAAI88), pages 475–479, 1988.
ψ1 ∈ min(≺1 ∗1 φ) [DP97] A. Darwiche and J. Pearl. On the logic of it-
ψ1 ∈ min(≺2 ∗2 φ) erated belief revision. Artificial Intelligence,
89(1-2):1–29, 1997.
..
. [EG92] T. Eiter and G. Gottlob. On the complexity
ψ1 ∈ min(≺n ∗n φ) of propositional knowledge base revision, up-
dates, and counterfactuals. Artificial Intelli-
where ≺i and ψi represent the epistemic state and the goal of gence, 57(2-3):227–270, 1992.
the agent i, respectively. Following the results in [Lib97], we
expect the complexity will be higher in this case. [FvD08] T. French and H. van Ditmarsch. Undecidabil-
ity for arbitrary public announcement logic. In
6.2 Conclusion Advances in Modal Logic, pages 23–42, 2008.
We have considered arbitrary public announcements in the [JT07] Y. Jin and M. Thielscher. Iterated belief revi-
setting of propositional belief revision. We have proved that sion, revised. Artificial Intelligence, 171(1):1–
the decision problem for arbitrary announcements in this set- 18, 2007.
ting is computationally simpler than it is in a modal setting,
even under very strong simplifying assumptions. We suggest [KM92] H. Katsuno and A.O. Mendelzon. Proposi-
that this result is important, because revision by announce- tional knowledge base revision and minimal
ments can be used in practical applications where the notion change. Artificial Intelligence, 52(2):263–294,
of fully nested beliefs is not required. We are currently de- 1992.
veloping a demonstration of this fact, in the context of simple [Lib97] Paolo Liberatore. The complexity of iterated
robot controllers. belief revision. In Proceedings of the 6th In-
ternational Conference on Database Theory,
References pages 276–290, 1997.
[AGM85] C.E. Alchourrón, P. Gärdenfors, and [VB07] Johan Van Benthem. Dynamic logic for belief
D. Makinson. On the logic of theory revision. Journal of applied non-classical log-
change: Partial meet functions for contraction ics, 17(2):129–155, 2007.
and revision. Journal of Symbolic Logic, [vDvdHK04] Hans van Ditmarsch, Wiebe van der Hoek,
50(2):510–530, 1985. and Barteld Kooi. Public announcements
[BBvD+ 07] P. Balbiani, A. Baltag, H. van Ditmarsch, and belief expansion. Proceedings of AiML-
A. Herzig, T. Hoshi, and T. De Lima. What 2004 (Advances in Modal Logic), University
can we achieve by arbitrary announcements? a of Manchester, pages 62–73, 2004.
dynamic take on fitch’s knowability. In Pro- [vDvdHK08] H. van Ditmarsch, W. van der Hoek, and
ceedings of the Conference on Theoretical As-
B. Kooi. Dynamic Epistemic Logic. Springer,
pects of Rationality and Knowledge (TARK-
2008.
07), pages 42–51, 2007.