WorksComputer Science
Going Deep Inside Public Announcement Logic
Abstract
Dynamic Epistemic Logic (DEL) is a family of logics that extend Epistemic Logic by adding dynamic modalities to the language, which represent communication and yield updates of knowledge. Among its various systems, Public Announcement Logic (PAL) provides a simple and interesting framework to analyse how knowledge gets updated through public communication. While its semantics has been extensively studied, its proof-theory remains more fragmented. In particular, the structural analysis of the announcements and their composition is yet to be refined. Deep inference naturally appears as well suited proof formalism when it comes to decompose formulas from the inside. It also offers a formalism with less syntax, that dispenses with bureaucracy. This paper presents the first deep inference proof system for PAL, using the formalism of open deduction. We show soundness, completeness, and cut admissibility for the new system.
https://www.lix.polytechnique.fr/Labo/Lutz.Strassburger/
Introduction
Dynamic Epistemic Logic (DEL) is a cohesive family of logical systems that represent knowledge and its change through communication. DEL extends static Epistemic Logic (EL), introduced by [32], with additional dynamic modalities used to represent communication events, or epistemic actions, such as public communication, semi-private communication to a group, private calls, etc. This means that, adding different such modalities yields different logical systems. Among them, the simplest and most studied is Public Announcement Logic (PAL), introduced first in [46] and then independently in [24]. PAL extends EL with a single dynamic modality that represents so-called public announcements, where means that after any truthful announcement1 of , we have that holds.
Despite its apparent simplicity, PAL captures interesting properties of dynamics and knowledge, both at a conceptual and at a technical level, and has been used to solve famous problems like the Muddy Children puzzle [22, 23]. Although PAL is as expressive as EL, it is shown to be exponentially more succinct (see [22]) while having the same computational complexity as EL (see [40]), and therefore provides a more convenient and handy framework to study knowledge acquisition. PAL has also been extended in various ways to capture several phenomena related to public communication in multi-agent systems, e.g. considering arbitrary announcements [4, 5, 12], studying group announcements [2, 58, 1] and group knowledge [13, 57] or investigating asynchronous announcements [33, 7, 9]. Other AI-related applications of DEL are epistemic planning [15] and reasoning about knowledge in distributed systems [11].
The semantics of PAL has been extensively studied (see, e.g., [46, 11, 22]). Epistemic modalities behave like S5-modalities, i.e., each agent is associated with an equivalence relation, representing their uncertainty. Then, public announcements act as model updaters by restricting the set of possible worlds, eliminating all those which do not satisfy the formula being announced. When updating a model with announcement , we therefore retain only the worlds which survive the announcement. The epistemic model then progressively shrinks as successive announcements are made.
While the semantics is well-understood, the proof-theory of PAL is a bit more fragmented. Its Hilbert-style axiomatisation (cf. [46, 22, 13]) extends that of multi-agent S5 with reduction axioms, e.g. , that allow to eliminate all dynamic modalities and translate any PAL-formula into an equivalent static EL-formula (that can be exponentially larger [22]).2 However, such an axiomatisation is of little use when it comes to finding proofs or studying their structural properties. In the last decade, several analytic proof systems have been proposed for PAL. Most of them either use inference rules that incorporate semantic reasoning on labels—this concerns the tableaux systems of [14, 8] and the labelled sequent calculus of [44]—or use inference rules that simulate reduction axioms—as done by the labelled sequent calculus in [59] and the non-labelled sequent calculus in [38]. In order to obtain a label-free system that does not rely on reduction axioms, the work in [35] proposed dynamic hypersequents that simulate the dynamics of announcements directly in the syntax.
In this paper, we propose an alternative route that is based on deep inference[26, 28, 18]. In contrast to traditional proof formalisms that only allow shallow inferences, deep inference allows applying inference rules at any depth inside a formula. It has been successfully employed for classical logic [18, 16, 17, 19], intuitionistic logic [54, 25, 30], various modal logics [31, 50], linear logic [51], and many others, in particular, the logic BV [26], for which there cannot be a shallow inference system [55]. Deep inference not only dispenses with heavy syntax and bureaucracy, providing more flexibility in the design of inference rules, it also gives alternative (and sometimes simpler) proofs of important theorems (e.g. focusing [21] and interpolation [52]).
In order to reduce the syntactic bureaucracy even more, we base our proof system OPAL on open deduction [27]. We then show soundness, completeness, and cut admissibility of this system via the hypersequent system of [35], mentioned above. This makes the comparison between the two formalisms clear: hypersequent rules behave as huge inference steps that can be decomposed into smaller ones, represented by the deep inference rules. To simplify the presentation, we confine ourselves here to the single-agent version of PAL, as done in [35]. Since PAL is conservative over S5, our proof system is also a new deep inference proof system for S5, which is surprisingly different from the one presented in [50].
The rest of the paper is organised as follows. Section 2 introduces the syntax and semantics of PAL, and Section 3 presents HPAL, a one-sided version of the hypersequent calculus of [35]. Then, in Section 4 we present our open deduction system OPAL. Soundness and completeness are shown with respect to HPAL in Section 5 and Section 6, respectively. Finally, in Section 7 we show that the cut is admissible in OPAL, by relying on the corresponding result for HPAL.
Syntax and Semantics of PAL
We give a brief introduction to the syntax, semantics and Hilbert-style axiomatisation of the single-agent fragment of Public Announcement Logic (PAL). This is a mere adaptation of the standard presentation as is can be found, for example, in [22, 35].
The formulas are generated from a countable set of atoms via the following grammar:
where and are units, and and are called epistemic modalities, and and are called announcement modalities. We consider formulas only in negation normal form to simplify the presentation and to ease the readability of the proof systems in this paper. Then, negation is defined for all formulas via De Morgan dualities:
It follows that for all formulas , and we define implication as and equivalence as .
The axioms of PAL are the axioms of classical propositional logic, together with the following axioms (where can be any atom, negated atom, or unit):
where the axioms on the left are the called K, T, and 5, respectively, and they define the classical modal logic S5. The axioms on the right in (3) are called reduction axioms.3
The theorems of the logic PAL are the formulas that can be derived from the axioms in (3) using the rules of modus pones and necessitation, shown below:
We write iff is a theorem of PAL.
Lemma 2.1. The following formulas are theorems of PAL:
Proof. They all follow by straightforward derivations.
Theorem 2.2. For every formula there is a formula with such that does not contain any announcement modalities.
Proof. This can be shown by induction on , by repeatedly applying Lemma 2.1.
Let us now turn to the semantics of PAL, which is, as expected, based on the standard Kripke semantics for modal logics [34].
Definition 2.3. An (epistemic) model is a tuple where is a set of possible worlds, and is an equivalence relation (i.e., transitive, symmetric, and reflexive), called the accessibility relation, and is the valuation function mapping each world to the set of atoms that are true at .
Definition 2.4. Let be an epistemic model. We now define the forcing relation and the updated model simultaneously by induction on , as shown below:
We write iff does not hold. In particular, we always have and it follows that iff , for all formulas . We say that is valid, denoted as , iff we have for every model and every world in that model.
Remark 2.5. Observerve that from this definition it follows that for all formulas and , we have that implies .
The following has been shown in e.g. [22].
Theorem 2.6. For all formulas , we have that iff .
Hypersequents for PAL
We now present a one-sided version of the hypersequent calculus from [35]. Here, a one-sided sequent is a finite, possibly empty, multiset of formulas, separated by comma, i.e., a sequent is written as for some . An announcement is a finite, possibly empty list of formulas, separated by a dot, i.e., an announcement is written as for some . For an announcement and a formula , we define the formulas and inductively as follows:
where is the empty list of formulas.
Definition 3.1. A dynamic sequent is an expression for some where are announcements and are sequents, and where for all $1 \le i < j \le n$. For we write for . In particular, then every sequent is a dynamic sequent. If for some are dynamic sequents, then is a dynamic hypersequent (DHS). In particular, every dynamic sequent is a DHS.
We can define the formula interpretation of sequents and hypersequents as follows. For a sequent , we have
For a dynamic sequent , we have
And for a dynamic hypersequent we have
Figure 1 shows the inference rules for the proof system HPAL, which is the hypersequent proof system of [35] translated into a one-sided version, using the De Morgan dualities shown in (2). We say that a DHS is provable in HPAL, written as , if there is a derivation of in HPAL.
Observe that every formula is also a DHS.
Lemma 3.2. Every DHS of the form is derivable in HPAL.
Proof. By straightforward induction on .
Lemma 3.3. For every DHS we have iff .
Proof. By routine induction on .
Theorem 3.4 ([35]). HPAL is sound and complete for PAL, i.e., iff .
where we have the following side conditions:
in : abbreviates and abbreviates , and does not appear in for any non-empty prefix of ;
in and : does not appear in ;
in : does not appear in ;
in : can be any atom, negated atom, or unit.

Figure 1. The hypersequent calculus HPAL
We end this section by stating that the cut rule
is admissible in HPAL. Here, the merge of two dynamic sequents and is defined as follows: if and , then is obtained by merging any two components and whenever , resulting in , and simply juxtaposing the others. Consequently, if and the resulting dynamic sequent is . For instance, if and (where are distinct) then . For more details, see [35 §4].
Theorem 3.5 ([35]). The (cut)-rule is admissible in HPAL.
Proof. For the one-sided version of the proof system, as we presented it here, the proof is exactly the same as for the two-sided version, as presented in [35 §6]. ▫
We will write whenever is provable in HPAL extended with the (cut)-rule. We then have immediately the following.
Corollary 3.6. If then .
A Deep Inference System for PAL
After having presented the hypersequent system HPAL, we now present the open deduction system OPAL for public announcement logic. Here, the inference rules operate directly on the formulas (as defined in § 2), so that we do not need to introduce another syntactic construct. The basic idea of open deduction [27] is that derivations are constructed by the same operations as formulas, together with a vertical composition via inference rules. For OPAL, the inference rules are shown in Figure 2. The rule uses the equivalence relation on formulas, which is defined to be the smallest congruence relation obeying

Figure 2. The open deduction system OPAL for Public Announcement Logic
for all formulas , , .
Definition 4.1. The set of derivations in OPAL is defined inductively together with the functions premise and conclusion from derivations to formulas, denoted by and , respectively, where we use the notation to denote a derivation with premise and conclusion .
– If is a formula, then is a derivation with .
– If and are derivations, then so is where , and and .
– If is a derivation, then so is where and is a formula, and and .
– If and are derivations, then so is where is an instance of an inference rule, and and .
If is a derivation with and , using only rules from a proof system X, then we denote this as . If , then we can also write .
† where can be any atom, negated atom, or unit
Definition 4.2. A rule is derivable in a system X iff there is a derivation .
One of the crucial properties of the OPAL proof system is that the general identity rule i, shown top-left in Figure 3, is derivable. This is similar to many sequent calculus proof systems. But deep inference allows also the other rules in Figure 3 to be derivable.
Figure 3. Additional derivable rules of OPAL
Lemma 4.3. The rules shown in Figure 3 are all derivable in OPAL.
Proof. For the rule i, this is a straightforward induction on . The rules , , , and , can be derived by a simple combination of w, c, and the modal rules. The remaining rules need an induction on . Details can be found in Appendix § 9.
Definition 4.4. A context is a formula in which one atom- or unit-occurrence is replaced by a hole . More precisely, contexts are generated by the grammar
If is a context and is a formula, then is the formula obtained from by replacing the hole by .
Deep inference allows to generalize this to derivations, i.e., if is a derivation with premise and conclusion , and a context, then we can construct, by induction on , the following derivation
with premise and conclusion .
Soundness
For showing soundness of OPAL, we have to show that (i) every inference rule of OPAL, shown in Figure 2 is sound (done in Lemma 5.1 below), and (ii) each case in the inductive definition of derivations (Definition 4.1) preserves soundness (done in Theorem 5.2 below).
Lemma 5.1. For every rule of OPAL, we have and .
Proof. For the rules , ai, c, w, s, and in the first row of Figure 2, we have that follows immediately from propositional reasoning. For the rules e, k, k′, t, 4, 5 in the second row of Figure 2, the corresponding implications are theorems of the modal logic S5. The remaining implications can be easily shown either syntactically, using the reduction axioms in (3) and (5), or by semantic means. Then (and therefore also ) follows from Theorem 3.4. We can also show directly, from which then would follow. Here is the case for the rule p (where and exist by Lemma 3.2):
For the convenience of the reader, we show all cases in Appendix B.
Theorem 5.2. For every derivation , we have and .
Proof. We can show both, and by structural induction on the derivation (cf. Definition 4.1). In Appendix B we show the details for . Then follows by Corollary 3.6 and Theorem 3.4.
Corollary 5.3 (Soundness). If then .
Proof. Immediately from Theorem 5.2 since .
Corollary 5.4. If then .
Proof. Immediately from Corollary 5.3 and Theorem 3.4, or directly, with the same construction as in the proof of Theorem 5.2.
Completeness
To simplify the presentation of the completeness proof for OPAL, we first show some auxiliary lemmas about the properties of OPAL.
Lemma 6.1. For any formulas and , if then and .
Proof. Observe that the only rules that can have an as outermost connective in the conclusion are and . In order to deal with we define the notions of a -formula and -context as follows:
i.e., for every -formula , we have , and for every -context and formula , we have . We are now showing a more general statement: for any -context , if then and \delta$ of . We have the following cases how this derivation can be obtained:
(1):
(2):
(3):
In Case (1), we have , and we are done immediately, as is our desired derivation. In Cases (2) and (3), we apply the induction hypothesis to . Note that Case (3) subsumes the cases where instead of , we use one of the rules , , or , as in each case we have that premise and conclusion are equivalent modulo .
Lemma 6.2. For any formula , if then also .
Proof. The only rules that have a as outermost connective in the conclusion are , , 4 and 5. We proceed by induction on the derivation of and the formula , and we have the following cases:
In the first three cases we are done immediately. In Case 4, we proceed by induction hypothesis (as in the previous lemma), and in Case 5, we apply Lemma 6.1, to get and , to which we apply the induction hypothesis, to obtain and , from which we get immediately .
Definition 6.3. A tame context is a context in which the hole does not occur inside an , nor in the scope of a or modality, i.e., a tame context is generated by the grammar
Lemma 6.4. Let be a tame context and let and be formulas. Then there is a derivation
Proof. We construct by induction on . The case of is trivial. The cases for and and are as follows (respectively):
where exists by induction hypothesis, and the case is similar to .
Lemma 6.5. Let be a tame context and let be formulas for . Then there is a derivation
Proof. We proceed by induction on . The base case is . We can show by induction on that there is a derivation from to via:
and the inductive case follows immediately from Lemma 6.4. □
Lemma 6.6. For every HPAL inference rule
with , there is an OPAL derivation
Proof. We construct for each rule of HPAL. Note that for the axioms and (Ax), as well as for the branching rules , , , and , we make crucial use of Lemma 6.4 and Lemma 6.5. The most involved cases are the rules and (Recall), for which we show the derivation in Figure 4. For the convenience of the reader, a complete list is shown in Appendix § 11. □

Figure 4. OPAL-derivations for the HPAL rules () and (Recall)
Theorem 6.7. If then .
Proof. By induction on the HPAL derivation of the hypersequent , we can, by applying Lemma 6.6 at each step, construct an OPAL-derivation with conclusion . By Lemma 6.2, this yields . □
Corollary 6.8 (Completeness). If then .
Proof. Let be a formula with . By Theorem 3.4, we have . Then, by Theorem 6.7, we get . □
Cut Elimination
The general cut rule in deep inference systems is
It is dual to the i-rule shown in Figure 3, and therefore, soundness of the cut-rule follows immediately, and we can extend Theorem 5.2 as follows:
Theorem 7.1. If then .
This is enough to prove cut admissibility for OPAL:
Corollary 7.2. If then .
Proof. Immediately from Theorem 7.1, Corollary 3.6, and Theorem 6.7. □
Remark 7.3. Here, we have used the cut elimination theorem of the hypersequent system HPAL (proved in [35]) to prove cut elimination for OPAL. It is clear that the next step should be to prove this internally, without the detour via HPAL, using the methods from [16] and [53, 29]. In a deep inference system, cut elimination usually means that all up-rules can be eliminated, which are rules that are dual to the down-rules, that are needed for completeness. Unfortunately, at the moment, there is not even an internal cut elimination proof for a deep inference system for S5. To our knowledge, there are two cut-free systems for S5, the one we presented here and the one by Stouppa [50]. Even though, they both use essentially the same hypersequent system to show cut-free completeness, they are very different from each other. Their difference in the propositional part is merely cosmetic4, but their difference in the modal rules is more fundamental. Stouppa’s system does not need the -rule, which would be considered an up-rule in the system for S4, presented in [52]. Furthermore, Stouppa’s system uses the rules
which would be considered the up-rules for our system, whereas our rules t, 4, and 5 would be the up-rules for Stouppa’s system. To make things even more confusing, in the system for S4, presented in [52], the rules t and 4 are the down-rules, and the rules t′ and 4 are the up-rules. For this reason, we did not in this paper use the usual ↓- and ↑-symbols in the rule names, as it is common in deep inference [28, 18]. We have to leave it to future research to unravel the mystery of up and down for S5.
Conclusion
In this paper we presented an open deduction system for PAL, which is the first deep inference system for a dynamic epistemic logic. We established soundness and completeness in a way that allows the reader to compare it to the recently introduced hypersequent calculus [35]. Our work can be seen as the starting point for the investigation of the proof theory of DEL through the route of deep inference, as it opens up many research questions, some of which we briefly discuss below.
Multi-agent systems: The first obvious extension of our system would be to allow for more than one epistemic modality pair, i.e. we have a finite set of agents, and each agent has its own pair of modalities and . The inference rules are very easy to adjust (simply replace and in each rule in Figure 2 by and , respectively). For this, deep inference is better suited than hypersequents. However, the completeness proof for the multi-agent system would be a bit more involved, as there is no hypersequent system to which we can refer.
General epistemic actions: Another natural extension would be to consider not only public announcement but any possible epistemic action, and to provide an open deduction system for the full logic of epistemic action models [11, 22]. In this logic, communication is represented by action models , where is a finite set of epistemic actions that may be indistinguishable from the agents’ perspective, written as , and that can be executed only when their precondition is satisfied, i.e. when we have . This logic generalises PAL, as a public announcement can be represented by a model of only a single action with . The reduction axioms are similar to those of PAL but the one for the epistemic modality now becomes . It would be interesting to see how to extend OPAL for dealing with such more general epistemic actions. We could adopt the same methodology and show soundness, completeness and cut-elimination via the dynamic hypersequent calculus of [36] that extends the one for PAL [35].
Proof complexity: In this paper we translated between the hypersequent system HPAL and the open deduction system OPAL, and in the introduction we briefly mentioned other formalisms like tableaux, and labelled and non-labelled sequent calculi. An interesting question is how all these proof systems for PAL behave with each other with respect to the size of their proofs.
More deep inference: Normally, deep inference allows to apply inference rules anywhere inside a formula context. However, in Definition 4.1, we do not allow inferences inside the announcement formulas. The reason is that the validity of does not imply the validity of . However, if , then also .
This means that we could add the inference rule
with the proviso that we have . This raises the question if this could lead to shorter proofs.
Intuitionistic PAL: Although the underlying logic of dynamic epistemic logics is usually classical logic, we may also consider systems that employ intuitionistic logic as a basis, to represent a different kind of knowledge. There are several proposals in the literature for what Intuitionistic Public Announcement Logic (IPAL) could be. First, there is the work [41], which extends the intuitionistic logic IK [48, 49] and the logic MIPC [47, 20] with dynamic modalities for announcements. Apart from the Hilbert-style axiomatisation, that extends the one of IK (resp. of MIPC) with the same reduction axioms as for classical PAL, the only calculi that exist for this logic are the labelled sequent calculi of [10] and [43], and the non-labelled sequent calculus of [37]. Second, the work [6] proposes a generalisation of IPAL with a binary modality, with only a Hilbert-style axiomatisation. And third, there is the work [45], which extends intuitionistic epistemic logic IEL by [3] with public announcement modalities. For each of them, deep inference could provide simple proof systems, that do not need labels.
Interpolation: Since PAL is equivalent to (multi-modal) S5, it is known to satisfy Craig interpolation (if is a theorem then there is in the common vocabulary such that both and are also theorems). In fact, the syntactic proof of [39] for interpolation for PAL uses an adaption of Maehara’s method [42] to a non-labelled sequent calculus, where dynamic rules simulate reduction axioms, i.e., they translate PAL-formulas into announcement-free S5-formulas during proof search. Consequently, the interpolant is an announcement-free formula. However, if an interpolant of provides an explanation of the truth of , then one would expect such an explanation to be expressed in the same language as . In particular, announcements should appear in the interpolant if occurs in both and . But the interpolants computed in [39] do not display any announcement. Moreover, since the announcement-free translation of a PAL-formulas can be exponentially longer [22], the interpolant thereby obtained might be incredibly long, and translating it back into a PAL-formula might be computationally complex. Defining an algorithm that can compute the interpolant directly in the language of PAL is therefore valuable in itself. Since OPAL is cut-free, it naturally appears as a promising calculus for defining such an interpolation algorithm.
AI Disclaimer This paper has been written by humans for humans. No AI tool has been used in the research or writing process.
Missing proofs for Section 4
Lemma 4.3. The rules shown in Figure 3 are all derivable in OPAL.
Proof. For the identity rule i we proceed by induction on . When is an atom, we simply use the atomic identity rule ai. The other cases are handled with the following derivations.
For , , , and , we use the following derivations.
Finally, for , , and , we proceed by induction on . The case where is empty is trivial. For the inductive case, where , we use the induction hypothesis and the corresponding rules , , and . This is straightforward.
Missing proofs for Section 5
For proving that OPAL is sound with respect to HPAL, we need to show that whenever there is a derivation from to in OPAL then there is a proof of in HPAL. To do so, we first show that all inference rules of OPAL are sound.
Lemma 5.1. For every rule of OPAL, we have and .
Proof. We show that, for each rule in OPAL there is an HPAL derivation of . We consider here the dynamic rules (as for propositional and modal rules, this is straightforward). We show by means of the following derivations, where every exists by Lemma 3.2.
For we have the three following derivations, depending on whether is a (negated) atom or unit:
For we have:
For we have:
For we have:
For we have:
For we have:
For we have:
For we have:
We now need to prove that each possible way of composing derivations in OPAL (see Definition 4.1) preserves soundness (Theorem 5.2). This requires the use of several rules shown to be admissible in HPAL. We therefore first state some result about HPAL before proceeding.
Lemma B.1 [35]. The rules of internal and external weakening are height-preserving admissible in HPAL.
Finally, although not stated in [35], we further need to show that the so-called lift rule is admissible in HPAL. For defining this rule, let be a formula and be a dynamic hypersequent. The dynamic sequent is obtained by replacing all indices occurring in by . In particular, if , the resulting dynamic sequent is . If , the dynamic hypersequent is obtained by lifting all dynamic sequents occurring in it, i.e., . Now, the lift rule is:
Lemma B.2. The lift rule is height-preserving admissible in HPAL.
Proof. The proof proceeds by induction on the height of a derivation of the premise. If is an axiom, then so is . Otherwise, we consider the last applied rule in the derivation: we apply the induction hypothesis to the premise(s) of and then apply again. This is straightforward. For the sake of clarity, the case where the last rule is an instance of is provided below.
The other cases are similar.
Remark B.3. The admissibility of the lift rule allows to show that necessitation for announcements, as in the alternative axiomatisation provided in [56] is admissible in HPAL. Since OPAL allows the construction of a derivation of from a derivation of , it is not surprising that one needs to simulate the necessitation of announcement to show that OPAL is sound.
Theorem 5.2. For every derivation , we have and .
Proof. Let be a derivation from to in OPAL. In the following we show that (we then get by applying , and follows from Corollary 3.6 and Theorem 3.4).
We proceed by induction on the derivation , and we have the following cases:
(i) If is a formula, then and by Lemma 3.2.
(ii) Suppose where . We only show the case where (the case of is treated similarly), for which we need to show . By induction hypothesis and . By Lemma B.1 we can use weakening, and obtain the desired result by the following derivation.
(iii) Suppose where . We first show the case where and then the case where (those with and are treated similarly).
If , we need to show . By induction hypothesis . By Lemma B.1 we can use external weakening, and obtain the desired result by the following derivation.
If , we need to show . By induction hypothesis . Here we use Lemma B.2 together with Lemma B.1 and reach the desired result by the following derivation, where exists by Lemma 3.2 and $\pi_2 exists by induction hypothesis.
(iv) Finally, suppose where is an instance of an inference rule.
We need to show . By induction hypothesis we have and . Moreover, by Lemma 5.1 we have . By Theorem 3.5 we can use (cut) twice to obtain the desired conclusion as follows:
Missing proof for Section 6
Lemma 6.6. For every HPAL inference rule
with , there is an OPAL derivation
Proof. We construct for each rule of HPAL.
For (T), we use for the base case of Lemma 6.5.
For (Ax), we have as follows:
where is again the base case of the proof of Lemma 6.5.
For , is the identity derivation:
For , directly obtained from Lemma 6.4:
For we have
For , we have
For we have
– For
we have
where , and is obtained from Lemma 6.5, and is the derivation
– for , we have
– for we have
– for we have
where exists by Lemma 6.4.
– For we have
where exists by Lemma 6.4.
– For (Atom) we construct
– For (New), we have
– For (Recall) we have
References
- [1]Ágotnes, T., Alechina, N., Galimullin, R.: Logics with group announcements and distributed knowledge: Completeness and expressive power. T. Ágotnes et al. Journal of Logic, Language and Information 31(2), 141–166 (2022)
- [2]Ágotnes, T., Balbiani, P., van Ditmarsch, H., Seban, P.: Group announcement logic. Journal of Applied Logic 8(1), 62–81 (2010)
- [3]Artemov, S., Protopopescu, T.: Intuitionistic epistemic logic. The Review of Symbolic Logic 9(2), 266–298 (2016)
- [4]Balbiani, P., Baltag, A., van Ditmarsch, H., Herzig, A., Hoshi, T., De Lima, T.: What can we achieve by arbitrary announcements? a dynamic take on fitch’s knowability. In: Proceedings of the 11th conference on Theoretical aspects of rationality and knowledge. pp. 42–51 (2007)
- [5]Balbiani, P., Baltag, A., van Ditmarsch, H., Herzig, A., Hoshi, T., De Lima, T.: Knowable’as ’known after an announcement. The Review of Symbolic Logic 1(3), 305–334 (2008)DOI
- [6]Balbiani, P., van Ditmarsch, H., Gencer, C., Lerouillois, C.: A minimal intuitionistic public announcement logic (2026)arxiv.org/abs/2611.14408
- [7]Balbiani, P., van Ditmarsch, H., González, S.F.: Asynchronous announcements. ACM Transactions on Computational Logic (TOCL) 23(2), 1–38 (2022)arxiv.org/abs/1705.03392
- [8]Balbiani, P., van Ditmarsch, H., Herzig, A., de Lima, T.: Tableaux for public announcement logics. Journal of Logic and Computation 20(1), 55–76 (2010)
- [9]Balbiani, P., van Ditmarsch, H., Lerouillois, C.: Axiomatisation for an asynchronous epistemic logic with sending and receiving messages. arXiv preprint arXiv:2510.02890 (2025), submitted to LMCSarxiv.org/abs/2510.02890
- [10]Balbiani, P., Galmiche, D.: About intuitionistic public announcement logic. In: 11th conference on Advances in Modal logic (AiML 2016). pp. 97–116. College Publications (2016)
- [11]Baltag, A., Moss, L., Solecki, S.: The logic of public announcements, common knowledge, and private suspicions. In: Gilboa, I. (ed.) Proceedings of the 7th Conference on Theoretical Aspects of Rationality and Knowledge (TARK VII). pp. 43–56 (1998)
- [12]Baltag, A., Özgün, A., Sandoval, A.L.V.: Arbitrary public announcement logic with memory. Journal of Philosophical Logic 52(1), 53–110 (2023)DOI
- [13]van Benthem, J., van Eijck, J., Kooi, B.: Logics of communication and change. Information and computation 204(11), 1620–1662 (2006)
- [14]de Boer, M.: Ke tableaux for public announcement logic. In: Formal Approaches to Multi-Agent Systems Workshop (FAMAS’007) (2007)
- [15]Bolander, T., Andersen, M.B.: Epistemic planning for single-and multi-agent systems. Journal of Applied Non-Classical Logics 21(1), 9–34 (2011)DOI
- [16]Brünnler, K.: Cut elimination inside a deep inference system for classical predicate logic. Studia Logica 82(1), 51–71 (2006)
- [17]Brünnler, K.: Locality for classical logic. Notre Dame Journal of Formal Logic 47(4), 557–580 (2006), http://www.iam.unibe.ch/~kai/Papers/LocalityClassical.pdf
- [18]Brünnler, K., Tiu, A.F.: A local system for classical logic. In: Nieuwenhuis, R., Voronkov, A. (eds.) LPAR 2001. LNAI, vol. 2250, pp. 347–361. Springer (2001)
- [19]Bruscoli, P., Guglielmi, A.: On the proof complexity of deep inference. ACM Transactions on Computational Logic 10(2), 1–34 (2009), article 14
- [20]Bull, R.: Mipc as the formalisation of an intuitionist concept of modality. The Journal of Symbolic Logic 31(4), 609–616 (1997)DOI
- [21]Chaudhuri, K., Guenot, N., Straßburger, L.: The focused calculus of structures. In: Bezem, M. (ed.) CSL’11. LIPIcs, vol. 12, pp. 159–173. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik (2011)DOI
- [22]van Ditmarsch, H., Hoek, W., Kooi van Der, B.: Dynamic epistemic logic, vol. 337. Springer Science & Business Media (2007)
- [23]van Ditmarsch, H., Kooi, B.: One hundred prisoners and a light bulb. In: One Hundred Prisoners and a Light Bulb, pp. 83–94. Springer (2015)
- [24]Gerbrandy, J., Groenveld, W.: Reasoning about information change. Journal of logic, language and information 6, 147–169 (1997)DOI
- [25]Guenot, N., Straßburger, L.: Symmetric normalisation for intuitionistic logic. In: Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). pp. 1–10 (2014)DOI
- [26]Guglielmi, A.: A system of interaction and structure. ACM Transactions on Computational Logic 8, 1 (01 2007). https://doi.org/10.1145/1182613.1182614
- [27]Guglielmi, A., Gundersen, T., Parigot, M.: A Proof Calculus Which Reduces Syntactic Bureaucracy. In: Lynch, C. (ed.) Proceedings of the 21st International Conference on Rewriting Techniques and Applications. Leibniz International Proceedings in Informatics (LIPIcs), vol. 6, pp. 135–150. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2010). https://doi.org/10.4230/LIPIcs.RTA.2010.135, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2010.135
- [28]Guglielmi, A., Straßburger, L.: Non-commutativity and MELL in the calculus of structures. In: Fribourg, L. (ed.) Computer Science Logic, CSL 2001. LNCS, vol. 2142, pp. 54–68. Springer-Verlag (2001)DOI
- [29]Guglielmi, A., Straßburger, L.: A system of interaction and structure V: the exponentials and splitting. Mathematical Structures in Computer Science 21(3), 563–584 (2011)DOI
- [30]Gundersen, T., Heijltjes, W., Parigot, M.: Atomic lambda calculus: A typed lambda-calculus with explicit sharing. In: 28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25-28, 2013. pp. 311–320. IEEE Computer Society (2013)DOI
- [31]Hein, R., Stewart, C.: Purity through unravelling. In: Bruscoli, P., Lamarche, F., Stewart, C. (eds.) Structures and Deduction. pp. 126–143. Technische Universität Dresden (2005), http://bitschnitzer.de/rh+cas--sd05.pdf, iCALP Workshop. ISSN 1430-211X
- [32]Hintikka, J.: Knowledge and belief: An introduction to the logic of the two notions. Studia Logica 16 (1962)
- [33]Knight, S., Maubert, B., Schwarzenruber, F.: Reasoning about knowledge and messages in asynchronous multi-agent systems. Mathematical Structures in Computer Science 29(1), 127–168 (2019)
- [34]Kripke, S.A.: A completeness theorem in modal logic. The Journal of Symbolic Logic 24(1), 1–14 (1959). https://doi.org/10.2307/2964568
- [35]Lerouvillois, C., Pogg iolesi, F.: Dynamic hypersequents for public announcement logic. The Review of Symbolic Logic 19(3), 491–518 (2026). https://doi.org/10.1017/S175502032610121X
- [36]Lerouvillois, C., Poggiolesi, F.: Dynamic proof theory for dynamic epistemic logic (2026), https://arxiv.org/abs/2609.37440
- [37]Lin, Z., Gao, Z., Zhao, Z.: Gentzen sequent calculi for intuitionistic public announcement logic (11 2025)
- [38]Liu, S., Sano, K.: Non-labelled sequent calculi of public announcement expansions of k 45 and s 5. In: International Workshop on Logic, Rationality and Interaction. pp. 190–206. Springer (2023)
- [39]Liu, S., Sano, K.: Sequent calculi for public announcement logic and action model logic. Synthese 208(3), 106 (2026)DOI
- [40]Lutz, C.: Complexity and succinctness of public announcement logic. In: Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems. p. 137–143. AAMAS ’06, Association for Computing Machinery, New York, NY, USA (2006). https://doi.org/10.1145/1160633.1160657, https://doi.org/10.1145/1160633.1160657
- [41]Ma, M., Palmigiano, A., Sadrzadeh, M.: Algebraic semantics and model completeness for intuitionistic public announcement logic. Annals of Pure and Applied Logic 165(4), 963–995 (2014)
- [42]Maehara, S.: Craig no interpolation theorem. Suugaku 12, 235–237 (1960)
- [43]Nomura, S., Sano, K., Tojo, S.: A labelled sequent calculus for intuitionistic public announcement logic. In: Davis, M., Fehnker, A., McIver, A., Voronkov, A. (eds.) Logic for Programming, Artificial Intelligence, and Reasoning. pp. 187–202. Springer Berlin Heidelberg, Berlin, Heidelberg (2015)DOI
- [44]Nomura, S., Sano, K., Tojo, S.: Revising a labelled sequent calculus for public announcement logic. In: Structural Analysis of Non-Classical Logics: The Proceedings of the Second Taiwan Philosophical Logic Colloquium. pp. 131–157. Springer (2015)DOI
- [45]Pavlova, A.: Public announcements for intuitionistic epistemic logic. In: Proceedings of the 8th Workshop on Formal and Cognitive Reasoning. vol. 3242, pp. 29–40. CEUR-WS. org (2022)DOI
- [46]Plaza, J.: Logics of public announcements. In: Proceedings 4th international symposium on methodologies for intelligent systems. pp. 201–216 (1989)
- [47]Prior, A.N.: Time and modality. Oxford University Press (2003)
- [48]Servi, F.: Axiomatizations for some intuitionistic modal logics. Rendiconti del Seminario Matematico Università e Politecnico di Torino 42 (1984)
- [49]Simpson, A.K.: Proof theory and semantics of intuitionistic modal logic. Ph.D. thesis, University of Edinburgh. College of Science and Engineering (1994)
- [50]Stouppa, P.: A deep inference system for the modal logic S5. Studia Logica: An International Journal for Symbolic Logic 85(2), 199–214 (2007)DOI
- [51]Straßburger, L.: A local system for linear logic. In: Baaz, M., Voronkov, A. (eds.) Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2002. LNAI, vol. 2514, pp. 388–402. Springer-Verlag (2002), http://www.lix.polytechnique.fr/~lutz/papers/LocSysLinLog.pdf
- [52]Straßburger, L.: Interpolation via generalized splitting. arXiv preprint arXiv:2607.23798 (2026)
- [53]Straßburger, L., Guglielmi, A.: A system of interaction and structure IV: The exponentials and decomposition. ACM Trans. Comput. Log. 12(4), 23 (2011)
- [54]Tiu, A.: A local system for intuitionistic logic. In: Hermann, M., Voronkov, A. (eds.) LPAR 2006. Lecture Notes in Artificial Intelligence, vol. 4246, pp. 242–256. Springer-Verlag (2006), http://users.rsise.anu.edu.au/~tiu/localint.pdf
- [55]Tiu, A.F.: A system of interaction and structure II: The need for deep inference. Logical Methods in Computer Science 2(2), 1–24 (2006)DOI
- [56]Wang, Y., Cao, Q.: On axiomatizations of public announcement logic. Synthese 190(Suppl 1), 103–134 (2013)DOI
- [57]Wáng, Y.N., Ágotnes, T.: Public announcement logic with distributed knowledge. In: International Workshop on Logic, Rationality and Interaction. pp. 328–341. Springer (2011)
- [58]Wáng, Y.N., Ágotnes, T.: Public announcement logic with distributed knowledge: expressivity, completeness and complexity. Synthese 190(Suppl 1), 135–162 (2013)DOI
- [59]Wu, H., van Ditmarsch, H., Chen, J.: A labelled sequent calculus for public announcement logic. Studies in Logic 16(3), 89–107 (2023)arxiv.org/abs/2207.10262
