betaFeedback

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 [⋅][\cdot] that represents so-called public announcements, where [A]B[A]B means that after any truthful announcement1 of AA, we have that BB 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 AA, 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. [A]p↔(A→p)[A]p \leftrightarrow(A \to p), 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 P={p,q,…}\mathcal{P} = \{p,q,\ldots\} of atoms via the following grammar:

A,B:=⊤∣⊥∣p∣pˉ∣A∧B∣A∨B∣□A∣◊A∣[A]B∣⟨A⟩B(1)A,B := \top\mid\bot\mid p \mid\bar{p} \mid A \land B \mid A \lor B \mid\Box A \mid\Diamond A \mid[A]B \mid\langle A\rangle B \tag*{(1)}

where ⊤\top and ⊥\bot are units, and □\Box and ◊\Diamond are called epistemic modalities, and [⋅][\cdot] and ⟨⋅⟩\langle\cdot\rangle 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:

pˉ=p⊤ˉ=⊥A∧B‾=Aˉ∨Bˉ□A‾=◊Aˉ[A]B‾=⟨A⟩Bˉ⊥ˉ=⊤A∨B‾=Aˉ∧Bˉ◊A‾=□Aˉ⟨A⟩B‾=[A]Bˉ(2)\begin{aligned} \bar{p} &= p & \bar{\top} &= \bot& \overline{A \land B} &= \bar{A} \lor\bar{B} & \overline{\Box A} &= \Diamond\bar{A} & \overline{[A]B} &= \langle A\rangle\bar{B}\\ \bar{\bot} &= \top& \overline{A \lor B} &= \bar{A} \land\bar{B} & \overline{\Diamond A} &= \Box\bar{A} & \overline{\langle A\rangle B} &= [A]\bar{B} \tag*{(2)} \end{aligned}

It follows that for all formulas Aˉˉ=A\bar{\bar{A}} = A, and we define implication as A→B=Aˉ∨BA \to B = \bar{A} \lor B and equivalence as A↔B=(A→B)∧(B→A)A \leftrightarrow B = (A \to B) \land(B \to A).

The axioms of PAL are the axioms of classical propositional logic, together with the following axioms (where pp can be any atom, negated atom, or unit):

□(A→B)→(□A→□B)□A→A◊A→□◊A[A]p↔(A→p)[A]B↔(A→⟨A⟩B)[A](B∧C)↔([A]B∧[A]C)[A]□B↔(A→□[A]B)[A][B]C↔[A∧[A]B]C(3)\begin{aligned} \Box(A \to B) &\to(\Box A \to\Box B)\\ \Box A &\to A\\ \Diamond A &\to\Box\Diamond A \end{aligned} \qquad \begin{aligned} [A]p &\leftrightarrow(A \to p)\\ [A]B &\leftrightarrow(A \to\langle A\rangle B)\\ [A](B \land C) &\leftrightarrow([A]B \land[A]C)\\ [A]\Box B &\leftrightarrow(A \to\Box[A]B)\\ [A][B]C &\leftrightarrow[A \land[A]B]C \tag*{(3)} \end{aligned}

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:

AA→BBmpA□Anec(4)\frac{A \qquad A \to B}{B} \qquad\mathrm{mp} \qquad\qquad \frac{A}{\Box A} \qquad\mathrm{nec} \tag*{(4)}

We write ⊢PALA\vdash_{\mathrm{PAL}} A iff AA is a theorem of PAL.

Lemma 2.1. The following formulas are theorems of PAL:

⟨A⟩p↔(A∧p)⟨A⟩B↔(A∧[A]B)⟨A⟩(B∧C)↔(⟨A⟩B∧⟨A⟩C)⟨A⟩□B↔(A∧□[A]B)⟨A⟩⟨B⟩C↔⟨⟨A⟩B⟩C⟨A⟩(B∨C)↔(⟨A⟩B∨⟨A⟩C)⟨A⟩◊B↔A∧◊⟨A⟩B⟨A⟩[B]C↔(A∧[⟨A⟩B]C)[A](B∨C)↔([A]B∨[A]C)[A]◊B↔(A→◊⟨A⟩B)[A]⟨B⟩C↔(A→⟨⟨A⟩B⟩C)(5)\begin{aligned} \langle A\rangle p &\leftrightarrow(A \land p) \\ \langle A\rangle B &\leftrightarrow(A \land[A]B) \\ \langle A\rangle(B \land C) &\leftrightarrow(\langle A\rangle B \land\langle A\rangle C) \\ \langle A\rangle\Box B &\leftrightarrow(A \land\Box[A]B) \\ \langle A\rangle\langle B\rangle C &\leftrightarrow\langle\langle A\rangle B\rangle C \\ \langle A\rangle(B \lor C) &\leftrightarrow(\langle A\rangle B \lor\langle A\rangle C) \\ \langle A\rangle\Diamond B &\leftrightarrow A \land\Diamond\langle A\rangle B \\ \langle A\rangle[B]C &\leftrightarrow(A \land[\langle A\rangle B]C) \\ [A](B \lor C) &\leftrightarrow([A]B \lor[A]C) \\ [A]\Diamond B &\leftrightarrow(A \to\Diamond\langle A\rangle B) \\ [A]\langle B\rangle C &\leftrightarrow(A \to\langle\langle A\rangle B\rangle C) \tag*{(5)} \end{aligned}

Proof. They all follow by straightforward derivations. □\square

Theorem 2.2. For every formula AA there is a formula A′A' with ⊢PALA↔A′\vdash_{\mathrm{PAL}} A \leftrightarrow A' such that A′A' does not contain any announcement modalities.

Proof. This can be shown by induction on AA, by repeatedly applying Lemma 2.1. □\square

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 M=⟨W,∼,V⟩\mathcal{M}=\langle W,\sim,V\rangle where WW is a set of possible worlds, and ∼⊆W×W\sim\subseteq W\times W is an equivalence relation (i.e., transitive, symmetric, and reflexive), called the accessibility relation, and V:W→P(P)V:W\to\mathcal{P}(P) is the valuation function mapping each world w∈Ww\in W to the set of atoms that are true at ww.

Definition 2.4. Let M=⟨W,∼,V⟩\mathcal{M}=\langle W,\sim,V\rangle be an epistemic model. We now define the forcing relation M,w⊩A\mathcal{M},w\Vdash A and the updated model MA=⟨WA,∼A,VA⟩\mathcal{M}_A=\langle W_A,\sim_A,V_A\rangle simultaneously by induction on AA, as shown below:

M,w⊩⊤iffalwaysM,w⊩piffp∈V(w)M,w⊩pˉiffp∉V(w)M,w⊩A∧BiffM,w⊩A and M,w⊩BM,w⊩A∨BiffM,w⊩A or M,w⊩BM,w⊩□Aifffor all v with w∼v we have M,v⊩AM,w⊩◊Aiffthere is a v with w∼v such that M,v⊩AM,w⊩[A]Biffif M,w⊩A then MA,w⊩BM,w⊩⟨A⟩BiffM,w⊩A and MA,w⊩B(6)\begin{aligned} \mathcal{M},w\Vdash\top&\quad\text{iff}\quad\text{always}\\ \mathcal{M},w\Vdash p &\quad\text{iff}\quad p\in V(w)\\ \mathcal{M},w\Vdash\bar{p} &\quad\text{iff}\quad p\notin V(w)\\ \mathcal{M},w\Vdash A\land B &\quad\text{iff}\quad\mathcal{M},w\Vdash A\text{ and }\mathcal{M},w\Vdash B\\ \mathcal{M},w\Vdash A\lor B &\quad\text{iff}\quad\mathcal{M},w\Vdash A\text{ or }\mathcal{M},w\Vdash B\\ \mathcal{M},w\Vdash\Box A &\quad\text{iff}\quad\text{for all }v\text{ with }w\sim v\text{ we have }\mathcal{M},v\Vdash A\\ \mathcal{M},w\Vdash\Diamond A &\quad\text{iff}\quad\text{there is a }v\text{ with }w\sim v\text{ such that }\mathcal{M},v\Vdash A\\ \mathcal{M},w\Vdash[A]B &\quad\text{iff}\quad\text{if }\mathcal{M},w\Vdash A\text{ then }\mathcal{M}_A,w\Vdash B\\ \mathcal{M},w\Vdash\langle A\rangle B &\quad\text{iff}\quad\mathcal{M},w\Vdash A\text{ and }\mathcal{M}_A,w\Vdash B \tag*{(6)} \end{aligned}
WA={w∈W∣M,w⊩A}∼A=∼∩(WA×WA)VA(w)=V(w)(for all w∈WA)(7)\begin{aligned} W_A &= \{w\in W\mid\mathcal{M},w\Vdash A\}\\ \sim_A &= \sim\cap(W_A\times W_A)\\ V_A(w) &= V(w)\qquad\text{(for all }w\in W_A\text{)} \tag*{(7)} \end{aligned}

We write M,w⊮A\mathcal{M},w\nVdash A iff M,w⊩A\mathcal{M},w\Vdash A does not hold. In particular, we always have M,w⊮⊥\mathcal{M},w\nVdash\bot and it follows that M,w⊩Aˉ\mathcal{M},w\Vdash\bar{A} iff M,w⊮A\mathcal{M},w\nVdash A, for all formulas AA. We say that AA is valid, denoted as ⊩PALA\Vdash_{\mathrm{PAL}} A, iff we have M,w⊩A\mathcal{M},w\Vdash A for every model M\mathcal{M} and every world ww in that model.

Remark 2.5. Observerve that from this definition it follows that for all formulas AA and BB, we have that ⊩PALB\Vdash_{\mathrm{PAL}} B implies ⊩PAL[A]B\Vdash_{\mathrm{PAL}}[A]B.

The following has been shown in e.g. [22].

Theorem 2.6. For all formulas AA, we have that ⊢PALA\vdash_{\mathrm{PAL}} A iff ⊩PALA\Vdash_{\mathrm{PAL}} A.

Hypersequents for PAL

We now present a one-sided version of the hypersequent calculus from [35]. Here, a one-sided sequent Γ\Gamma is a finite, possibly empty, multiset of formulas, separated by comma, i.e., a sequent is written as A1,A2,…,AkA_1,A_2,\ldots,A_k for some k≥0k \ge0. An announcement α\alpha is a finite, possibly empty list of formulas, separated by a dot, i.e., an announcement is written as A1⋅A2⋅…⋅AhA_1 \cdot A_2 \cdot\ldots\cdot A_h for some h≥0h \ge0. For an announcement α\alpha and a formula BB, we define the formulas [α]B[\alpha]B and ⟨α⟩B\langle\alpha\rangle B inductively as follows:

[ε]B:=B⟨ε⟩B:=B[α⋅A]B:=[α][A]B⟨α⋅A⟩B:=⟨α⟩⟨A⟩B(8)\begin{aligned} [\varepsilon]B &:= B & \langle\varepsilon\rangle B &:= B\\ [\alpha\cdot A]B &:= [\alpha][A]B & \langle\alpha\cdot A\rangle B &:= \langle\alpha\rangle\langle A\rangle B \tag*{(8)} \end{aligned}

where ε\varepsilon is the empty list of formulas.

Definition 3.1. A dynamic sequent XX is an expression //α1Γ1//α2Γ2⋯//αnΓn//_{\alpha_1}\Gamma_1 \mathbin{//}_{\alpha_2}\Gamma_2 \cdots\mathbin{//}_{\alpha_n}\Gamma_n for some n≥1n \ge1 where α1,…,αn\alpha_1,\ldots,\alpha_n are announcements and Γ1,…,Γn\Gamma_1,\ldots,\Gamma_n are sequents, and where αi≠αj\alpha_i \ne\alpha_j for all $1 \le i < j \le n$. For α=ε\alpha= \varepsilon we write Γ\Gamma for //εΓ//_{\varepsilon}\Gamma. In particular, then every sequent Γ\Gamma is a dynamic sequent. If X1,…,XmX_1,\ldots,X_m for some m≥1m \ge1 are dynamic sequents, then G=X1∣X2∣…∣XmG = X_1 \mid X_2 \mid\ldots\mid X_m is a dynamic hypersequent (DHS). In particular, every dynamic sequent is a DHS.

We can define the formula interpretation (⋅)τ(\cdot)^\tau of sequents and hypersequents as follows. For a sequent Γ=A1,A2,…,Ak\Gamma= A_1,A_2,\ldots,A_k, we have

Γτ=(A1,A2,…,Ak)τ:=A1∨A2∨⋯∨Ak\Gamma^\tau= (A_1,A_2,\ldots,A_k)^\tau:= A_1 \lor A_2 \lor\cdots\lor A_k

For a dynamic sequent X=//α1Γ1//α2Γ2⋯//αkΓkX = //_{\alpha_1}\Gamma_1 \mathbin{//}_{\alpha_2}\Gamma_2 \cdots\mathbin{//}_{\alpha_k}\Gamma_k, we have

Xτ:=(//α1Γ1//α2Γ2⋯//αnΓn)τ=[α1]Γ1τ∨[α2]Γ2τ∨⋯∨[αn]ΓnτX^\tau:= (//_{\alpha_1}\Gamma_1 \mathbin{//}_{\alpha_2}\Gamma_2 \cdots\mathbin{//}_{\alpha_n}\Gamma_n)^\tau= [\alpha_1]\Gamma_1^\tau\lor[\alpha_2]\Gamma_2^\tau\lor\cdots\lor[\alpha_n]\Gamma_n^\tau

And for a dynamic hypersequent G=X1∣X2∣…∣XmG = X_1 \mid X_2 \mid\ldots\mid X_m we have

Gτ=(X1∣X2∣…∣Xm)τ:=□X1τ∨□X2τ∨⋯∨□XmτG^\tau= (X_1 \mid X_2 \mid\ldots\mid X_m)^\tau:= \Box X_1^\tau\lor\Box X_2^\tau\lor\cdots\lor\Box X_m^\tau

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 GG is provable in HPAL, written as ⊢HPALG\vdash_{\mathrm{HPAL}} G, if there is a derivation of GG in HPAL.

Observe that every formula AA is also a DHS.

Lemma 3.2. Every DHS of the form G∣X//αΓ,A,A‾G \mid X \mathbin{//}_{\alpha}\Gamma,A,\overline{A} is derivable in HPAL.

Proof. By straightforward induction on AA. □\square

Lemma 3.3. For every DHS GG we have ⊢HPALG\vdash_{\mathrm{HPAL}} G iff ⊢HPALGτ\vdash_{\mathrm{HPAL}} G^\tau.

Proof. By routine induction on GG. □\square

Theorem 3.4 ([35]). HPAL is sound and complete for PAL, i.e., ⊢HPALA\vdash_{\mathrm{HPAL}} A iff ⊢PALA\vdash_{\mathrm{PAL}} A.

\begin{aligned} &(\top)\ \frac{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,\mathsf{T}}{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,\mathsf{T}}} \qquad (\mathsf{Ax})\ \frac{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,\overline{p},p}{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,\overline{p},p}} \qquad (\vee)\ \frac{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,A,B}{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,A\vee B}} \qquad (\wedge)\ \frac{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,A}\quad\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,B}{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,A\wedge B}} \\ &(\Box)\ \frac{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma\vdash A}{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,\Box A}} \qquad (\Diamond\mathsf{T})\ \frac{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,\Diamond A,A}{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,\Diamond A}} \qquad (\Diamond5)\ \frac{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,\Diamond A\mid Y\mathbin{//_{\alpha}\Delta,A}{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,\Diamond A\mid Y\mathbin{//_{\alpha}\Delta}} \\ &(\Diamond\mathsf{P})\ \frac{\mathcal{G}'\mid Y\mathbin{//_{\alpha}\Delta,B_{1}}\quad\mathcal{G}'\mid Y\mathbin{//_{\alpha\cdot B_{1}}\Delta,B_{2}}\quad\mathcal{G}'\mid Y\mathbin{//_{\alpha\cdot B_{1}\cdot B_{2}}\Delta,B_{3}\quad\cdots\quad\mathcal{G}'\mid Y\mathbin{//_{\alpha\cdot B} \Delta,A}}{\mathcal{G}\mid X\mathbin{//_{\alpha\cdot\beta}\Gamma,\Diamond A\mid Y\mathbin{//_{\alpha}\Delta}} \\ &([\cdot]_{0})\ \frac{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,\overline{A}\mathbin{//_{\alpha\cdot A}B}{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,[A]B}} \qquad (\langle\cdot\rangle_{0})\ \frac{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,A\quad\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma\mathbin{//_{\alpha\cdot A}B}{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,\langle A\rangle B}} \\ &([\cdot]_{1})\ \frac{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,\overline{A}\mathbin{//_{\alpha\cdot A}\Delta,B}{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,[A]B\mathbin{//_{\alpha\cdot A}\Delta}} \qquad (\langle\cdot\rangle_{1})\ \frac{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,A\mathbin{//_{\alpha\cdot A}\Delta}\quad\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma\mathbin{//_{\alpha\cdot A}\Delta,B}{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,\langle A\rangle\mathbin{//_{\alpha\cdot A}\Delta}} \\ &(\operatorname{Atom})\ \frac{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,q\mathbin{//_{\alpha\cdot A}\Delta,q}{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma\mathbin{//_{\alpha\cdot A}\Delta,q}} \qquad (\operatorname{New})\ \frac{\mathcal{G}\mid X\mathbin{//_{\alpha}\mathbin{//_{\alpha\cdot A}\Delta}{\mathcal{G}\mid X\mathbin{//_{\alpha\cdot A}\Delta}} \qquad (\operatorname{Recall})\ \frac{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,\overline{A}\mathbin{//_{\alpha\cdot A}\Delta}{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma\mathbin{//_{\alpha\cdot A}\Delta}} \end{aligned}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

where we have the following side conditions:

in (◊P)(\Diamond\mathsf{P}): β\beta abbreviates B1⋅B2⋯BnB_{1}\cdot B_{2}\cdots B_{n} and G′\mathcal{G}' abbreviates G∣X//α⋅βΓ,◊A\mathcal{G}\mid X\mathbin{//_{\alpha\cdot\beta}\Gamma,\Diamond A}, and //α⋅β\mathbin{//_{\alpha\cdot\beta}} does not appear in YY for any non-empty prefix β′\beta' of β\beta;

in ([⋅]0)([\cdot]_{0}) and (⟨⋅⟩0)(\langle\cdot\rangle_{0}): //α⋅A\mathbin{//_{\alpha\cdot A}} does not appear in XX;

in (New⁡)(\operatorname{New}): //α\mathbin{//_{\alpha}} does not appear in XX;

in (Atom⁡)(\operatorname{Atom}): qq can be any atom, negated atom, or unit.

The hypersequent calculus HPAL

Figure 1. The hypersequent calculus HPAL

We end this section by stating that the cut rule

\frac{\mathcal{G}\mid X\mathbin{//_{\alpha}\Gamma,\mathcal{H}\mid Y\mathbin{//_{\alpha}A,\Delta}}{\mathcal{G}\mid\mathcal{H}\mid X\oplus Y\mathbin{//_{\alpha}\Gamma,\Delta}}} \tag*{(9)}

is admissible in HPAL. Here, the merge X⊕YX\oplus Y of two dynamic sequents XX and YY is defined as follows: if X=//α1Γ1//⋯//αnΓnX=\mathbin{//_{\alpha_{1}}\Gamma_{1}\mathbin{//}\cdots\mathbin{//_{\alpha_{n}}\Gamma_{n}}} and Y=//β1Δ1//⋯//βkΔkY=\mathbin{//_{\beta_{1}}\Delta_{1}\mathbin{//}\cdots\mathbin{//_{\beta_{k}}\Delta_{k}}}, then X⊕YX\oplus Y is obtained by merging any two components //αiΓi\mathbin{//_{\alpha_{i}}\Gamma_{i}} and //βjΔj\mathbin{//_{\beta_{j}}\Delta_{j}} whenever αi=βj\alpha_{i}=\beta_{j}, resulting in //αiΓi,Δj\mathbin{//_{\alpha_{i}}\Gamma_{i},\Delta_{j}}, and simply juxtaposing the others. Consequently, if X=X′//αΓX=X'\mathbin{//_{\alpha}\Gamma} and Y=Y′//αΔY=Y'\mathbin{//_{\alpha}\Delta} the resulting dynamic sequent is X⊕Y=X′⊕Y′//αΓ,ΔX\oplus Y=X'\oplus Y'\mathbin{//_{\alpha}\Gamma,\Delta}. For instance, if X=Γ//αΓ′//βΓ′′X=\Gamma\mathbin{//_{\alpha}\Gamma'\mathbin{//_{\beta}\Gamma''}} and Y=Δ//αΔ′//γΔ′′Y=\Delta\mathbin{//_{\alpha}\Delta'\mathbin{//_{\gamma}\Delta''}} (where α,β,γ\alpha,\beta,\gamma are distinct) then X⊕Y=Γ,Δ//αΓ′,Δ′//βΓ′′//γΔ′′X\oplus Y=\Gamma,\Delta\mathbin{//_{\alpha}\Gamma',\Delta'\mathbin{//_{\beta}\Gamma''\mathbin{//_{\gamma}\Delta''}}}. 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 ⊢HPAL+(cut)A\vdash_{\mathrm{HPAL}+\mathrm{(cut)}} A whenever AA is provable in HPAL extended with the (cut)-rule. We then have immediately the following.

Corollary 3.6. If ⊢HPAL+(cut)A\vdash_{\mathrm{HPAL}+\mathrm{(cut)}} A then ⊢HPALA\vdash_{\mathrm{HPAL}} A.

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 ≡\equiv uses the equivalence relation ≡\equiv on formulas, which is defined to be the smallest congruence relation obeying

The open deduction system OPAL for Public Announcement Logic

Figure 2. The open deduction system OPAL for Public Announcement Logic

(A∨B)∨C≡A∨(B∨C)A∨B≡B∨A⊥∨A≡A(10)(A \lor B) \lor C \equiv A \lor(B \lor C) \qquad A \lor B \equiv B \lor A \qquad\bot\lor A \equiv A \tag*{(10)}

for all formulas AA, BB, CC.

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 pr⁡(⋅)\operatorname{pr}(\cdot) and cn⁡(⋅)\operatorname{cn}(\cdot), respectively, where we use the notation Aδ∥B\frac{A}{\delta\parallel B} to denote a derivation δ\delta with premise pr⁡(δ)=A\operatorname{pr}(\delta)=A and conclusion cn⁡(δ)=B\operatorname{cn}(\delta)=B.

– If AA is a formula, then δ=A\delta=A is a derivation with pr⁡(δ)=cn⁡(δ)=A\operatorname{pr}(\delta)=\operatorname{cn}(\delta)=A.

– If Aθ∥B\frac{A}{\theta\parallel B} and Cζ∥D\frac{C}{\zeta\parallel D} are derivations, then so is δ=θ∗ζ=A∗Cθ∗ζ∥B∗D\delta=\theta\ast\zeta=\frac{A\ast C}{\theta\ast\zeta\parallel B\ast D} where ∗∈{∧,∨}\ast\in\{\land,\lor\}, and pr⁡(δ)=A∗C\operatorname{pr}(\delta)=A\ast C and cn⁡(δ)=B∗D\operatorname{cn}(\delta)=B\ast D.

– If Aθ∥B\frac{A}{\theta\parallel B} is a derivation, then so is δ=∘θ=∘A∘θ∥∘B\delta=\circ\theta=\frac{\circ A}{\circ\theta\parallel\circ B} where ∘∈{□, ^,[C],⟨C⟩}\circ\in\{\Box,\hat{\ },[C],\langle C\rangle\} and CC is a formula, and pr⁡(δ)=∘A\operatorname{pr}(\delta)=\circ A and cn⁡(δ)=∘B\operatorname{cn}(\delta)=\circ B.

– If Aθ∥B\frac{A}{\theta\parallel B} and Cζ∥D\frac{C}{\zeta\parallel D} are derivations, then so is δ=ρθζ=ρAθ∥BCζ∥D\delta=\rho\frac{\theta}{\zeta}=\rho\frac{\frac{A}{\theta\parallel B}}{\frac{C}{\zeta\parallel D}} where ρBC\rho\frac{B}{C} is an instance of an inference rule, and pr⁡(δ)=A\operatorname{pr}(\delta)=A and cn⁡(δ)=D\operatorname{cn}(\delta)=D.

If δ\delta is a derivation with pr⁡(δ)=A\operatorname{pr}(\delta)=A and cn⁡(δ)=B\operatorname{cn}(\delta)=B, using only rules from a proof system X, then we denote this as Aδ∥B∥X\frac{A}{\delta\parallel B}\mathbin{\|}X. If pr⁡(δ)=⊤\operatorname{pr}(\delta)=\top, then we can also write δ∥XB\frac{\delta\mathbin{\|}X}{B}.

⊤⊤⊤∧⊤ai ⊤pˉ∨pc A∨AAw ⊥As (A∨C)∧(B∨D)(A∨B)∨(C∧D)≡ BA (if A≡B)e ⊤□⊤k □(A∨B)□A∨◊Bk′ □A∧□B□(A∧B)t A◊A4 □A□□A5 ◊A□◊Ae[⋅]q[A]q†k[⋅][A](B∨C)[A]B∨⟨A⟩Ck[⋅]′[A]B∧[A]C[A](B∧C)k⟨⋅⟩⟨A⟩B[A]Bp⋄⟨A⟩B[A]◊Bp□□[A]B[A]□BrA∧[A]B⟨A⟩BnAˉ[A]B\begin{aligned} &\top\frac{\top}{\top\wedge\top} \qquad \mathrm{ai}\ \frac{\top}{\bar{p}\vee p} \qquad \mathrm{c}\ \frac{A\vee A}{A} \qquad \mathrm{w}\ \frac{\bot}{A} \qquad \mathrm{s}\ \frac{(A\vee C)\wedge(B\vee D)}{(A\vee B)\vee(C\wedge D)} \qquad \equiv\ \frac{B}{A}\ \text{(if }A\equiv B\text{)} \\ &\mathrm{e}\ \frac{\top}{\Box\top} \qquad \mathrm{k}\ \frac{\Box(A\vee B)}{\Box A\vee\Diamond B} \qquad \mathrm{k}'\ \frac{\Box A\wedge\Box B}{\Box(A\wedge B)} \qquad \mathrm{t}\ \frac{A}{\Diamond A} \qquad 4\ \frac{\Box A}{\Box\Box A} \qquad 5\ \frac{\Diamond A}{\Box\Diamond A} \\ &\mathrm{e}_{[\cdot]} \frac{q}{[A]q}^{\dagger} \qquad \mathrm{k}_{[\cdot]} \frac{[A](B\vee C)}{[A]B\vee\langle A\rangle C} \qquad \mathrm{k}'_{[\cdot]} \frac{[A]B\wedge[A]C}{[A](B\wedge C)} \qquad \mathrm{k}_{\langle\cdot\rangle}\frac{\langle A\rangle B}{[A]B} \\ &\mathrm{p}_{\diamond}\frac{\langle A\rangle B}{[A]\Diamond B} \qquad \mathrm{p}_{\Box}\frac{\Box[A]B}{[A]\Box B} \qquad \mathrm{r}\frac{A\wedge[A]B}{\langle A\rangle B} \qquad \mathrm{n}\frac{\bar{A}}{[A]B} \end{aligned}

† where qq can be any atom, negated atom, or unit

i ⊤Aˉ∨Am□□A∨□B□(A∨B)m□4□A∨□B□(A∨□B)m□5□A∨◊B□(A∨◊B)5∗□A∨□(C∨B)□(A∨B)∨□Cm[⋅]∗[α]B∨[α]C[α](B∨C)k[⋅]∗[α](B∨C)[α]B∨⟨α⟩Ck⟨⋅⟩∗⟨α⟩B[α]Bp⋄∗⟨α⟩B[α]◊Bp□∗□[α]B[α]□B\begin{aligned} &\mathrm{i}\ \frac{\top}{\bar{A}\vee A} \qquad \mathrm{m}_{\Box}\frac{\Box A\vee\Box B}{\Box(A\vee B)} \qquad \mathrm{m}_{\Box}^{4}\frac{\Box A\vee\Box B}{\Box(A\vee\Box B)} \qquad \mathrm{m}_{\Box}^{5}\frac{\Box A\vee\Diamond B}{\Box(A\vee\Diamond B)} \qquad 5^{*}\frac{\Box A\vee\Box(C\vee B)}{\Box(A\vee B)\vee\Box C} \\ &\mathrm{m}_{[\cdot]}^{*}\frac{[\alpha]B\vee[\alpha]C}{[\alpha](B\vee C)} \qquad \mathrm{k}_{[\cdot]}^{*}\frac{[\alpha](B\vee C)}{[\alpha]B\vee\langle\alpha\rangle C} \qquad \mathrm{k}_{\langle\cdot\rangle}^{*}\frac{\langle\alpha\rangle B}{[\alpha]B} \qquad \mathrm{p}_{\diamond}^{*}\frac{\langle\alpha\rangle B}{[\alpha]\Diamond B} \qquad \mathrm{p}_{\Box}^{*}\frac{\Box[\alpha]B}{[\alpha]\Box B} \end{aligned}

Definition 4.2. A rule ρ AB\rho\ \frac{A}{B} is derivable in a system X iff there is a derivation AB\frac{A}{B}.

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 AA. The rules m□\mathrm{m}_{\Box}, m□4\mathrm{m}_{\Box}^{4}, m□5\mathrm{m}_{\Box}^{5}, and 5∗5^{*}, can be derived by a simple combination of w, c, and the modal rules. The remaining rules need an induction on α\alpha. Details can be found in Appendix § 9. □\square

Definition 4.4. A context is a formula in which one atom- or unit-occurrence is replaced by a hole {⋅}\{\cdot\}. More precisely, contexts are generated by the grammar

C{⋅}:={⋅}∣A∧C{⋅}∣C{⋅}∧A∣A∨C{⋅}∣C{⋅}∨A∣□C{⋅}∣◊C{⋅}∣[A]C{⋅}∣⟨A⟩C{⋅}(11)C\{\cdot\}:=\{\cdot\}\mid A\wedge C\{\cdot\}\mid C\{\cdot\}\wedge A\mid A\vee C\{\cdot\}\mid C\{\cdot\}\vee A\mid\Box C\{\cdot\}\mid\Diamond C\{\cdot\}\mid[A]C\{\cdot\}\mid\langle A\rangle C\{\cdot\} \tag*{(11)}

If C{⋅}C\{\cdot\} is a context and AA is a formula, then C{A}C\{A\} is the formula obtained from C{⋅}C\{\cdot\} by replacing the hole {⋅}\{\cdot\} by AA.

Deep inference allows to generalize this to derivations, i.e., if δ\delta is a derivation with premise AA and conclusion BB, and C{⋅}C\{\cdot\} a context, then we can construct, by induction on C{⋅}C\{\cdot\}, the following derivation

δ′=C{δ}=C{Aδ//B}={C{A}C{δ}C{B}\delta' = C\{\delta\} = C\left\{\begin{array}{c} A \\ \delta\mathbin{//} \\ B \end{array}\right\} = \left\{\begin{array}{c} C\{A\} \\ C\{\delta\} \\ C\{B\} \end{array}\right.

with premise pr⁡(δ′)=C{A}\operatorname{pr}(\delta')=C\{A\} and conclusion cn⁡(δ′)=C{B}\operatorname{cn}(\delta')=C\{B\}.

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 ρ AB\rho\ \dfrac{A}{B} of OPAL, we have ⊢PALA→B\vdash_{\mathrm{PAL}} A \to B and ⊢HPALA‾,B\vdash_{\mathrm{HPAL}} \overline{A},B.

Proof. For the rules ⊤\top, ai, c, w, s, and ≡\equiv in the first row of Figure 2, we have that ⊢PALA→B\vdash_{\mathrm{PAL}} A \to B 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 ⊢HPALA‾∨B\vdash_{\mathrm{HPAL}} \overline{A} \lor B (and therefore also ⊢HPALA‾,B\vdash_{\mathrm{HPAL}} \overline{A},B) follows from Theorem 3.4. We can also show ⊢HPALA‾,B\vdash_{\mathrm{HPAL}} \overline{A},B directly, from which then ⊢PALA→B\vdash_{\mathrm{PAL}} A \to B would follow. Here is the case for the rule p□_\Box (where π1\pi_1 and π2\pi_2 exist by Lemma 3.2):

p_\Box\ \dfrac{\Box[A]B}{[A]\Box B} \quad\leadsto\quad \begin{array}{c} \overline{A},\Diamond\langle A\rangle\overline{B}\mathbin{//}_{A}\ A,\overline{A}\mathbin{//}_{A}\ B \\[4pt] \overset{(\langle\cdot\rangle_1)}{\dfrac{\overline{A},\Diamond\langle A\rangle\overline{B}\mathbin{//}_{A}\ A,\overline{A}\mathbin{//}_{A}\ B \qquad \overline{A},\Diamond\langle A\rangle\overline{B}\mathbin{//}_{A}\ A\mathbin{//}_{A}\ B,\overline{B}} {\overline{A},\Diamond\langle A\rangle\overline{B}\mathbin{//}_{A}\ \langle A\rangle\overline{B},\overline{A}\mathbin{//}_{A}\ B} \\[4pt] \overset{(\wedge5)}{\dfrac{\overline{A},\Diamond\langle A\rangle\overline{B}\mathbin{//}_{A}\ \langle A\rangle\overline{B},\overline{A}\mathbin{//}_{A}\ B} {\overline{A},\Diamond\langle A\rangle\overline{B}\mathbin{//}_{A}\ \overline{A}\mathbin{//}_{A}\ B}} \\[4pt] \overset{(\mathrm{New})+(\mathrm{Recall})}{\dfrac{\overline{A},\Diamond\langle A\rangle\overline{B}\mathbin{//}_{A}\ \overline{A}\mathbin{//}_{A}\ B} {\overline{A},\Diamond\langle A\rangle\overline{B}\mathbin{//}_{A}\ \mathbin{//}_{A}\ B}} \\[4pt] \overset{(\Box)}{\dfrac{\overline{A},\Diamond\langle A\rangle\overline{B}\mathbin{//}_{A}\ \mathbin{//}_{A}\ B} {\overline{A},\Diamond\langle A\rangle\overline{B}\mathbin{//}_{A}\ \Box B}} \\[4pt] \overset{([\,\cdot\,]_0)}{\dfrac{\overline{A},\Diamond\langle A\rangle\overline{B}\mathbin{//}_{A}\ \Box B} {\Diamond\langle A\rangle\overline{B},\overline{A}\Box B}} \end{array}}

For the convenience of the reader, we show all cases in Appendix B. □\square

Theorem 5.2. For every derivation δ//OPALAB\delta\mathbin{//}_{\mathrm{OPAL}} \dfrac{A}{B}, we have ⊢PALA→B\vdash_{\mathrm{PAL}} A \to B and ⊢HPAL+(cut)A‾,B\vdash_{\mathrm{HPAL+ (cut)}} \overline{A},B.

Proof. We can show both, ⊢PALA→B\vdash_{\mathrm{PAL}} A \to B and ⊢HPAL+(cut)A‾,B\vdash_{\mathrm{HPAL+(cut)}} \overline{A},B by structural induction on the derivation δ\delta (cf. Definition 4.1). In Appendix B we show the details for ⊢HPAL+(cut)A‾,B\vdash_{\mathrm{HPAL+(cut)}} \overline{A},B. Then ⊢PALA→B\vdash_{\mathrm{PAL}} A \to B follows by Corollary 3.6 and Theorem 3.4. □\square

Corollary 5.3 (Soundness). If ⊢OPALA\vdash_{\mathrm{OPAL}} A then ⊢PALA\vdash_{\mathrm{PAL}} A.

Proof. Immediately from Theorem 5.2 since A↔(⊤→A)A \leftrightarrow(\top\to A).

Corollary 5.4. If ⊢OPALA\vdash_{\mathrm{OPAL}} A then ⊢HPALA\vdash_{\mathrm{HPAL}} A.

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 AA and BB, if ⊢OPALA∧B\vdash_{\mathrm{OPAL}} A \land B then ⊢OPALA\vdash_{\mathrm{OPAL}} A and ⊢OPALB\vdash_{\mathrm{OPAL}} B.

Proof. Observe that the only rules that can have an ∧\land as outermost connective in the conclusion are ⊤\top and ≡\equiv. In order to deal with ≡\equiv we define the notions of a ⊥\bot-formula A⊥A^{\bot} and ⊥\bot-context C⊥{⋅}C^{\bot}\{\cdot\} as follows:

A⊥≔⊥∣A⊥∨⊥∣⊥∨A⊥A^{\bot} \coloneqq\bot\mid A^{\bot} \lor\bot\mid\bot\lor A^{\bot}
C⊥{⋅}≔{⋅}∣A⊥∨C⊥{⋅}∣C⊥{⋅}∨A⊥C^{\bot}\{\cdot\} \coloneqq\{\cdot\} \mid A^{\bot} \lor C^{\bot}\{\cdot\} \mid C^{\bot}\{\cdot\} \lor A^{\bot}

i.e., for every ⊥\bot-formula A⊥A^{\bot}, we have A⊥≡⊥A^{\bot} \equiv\bot, and for every ⊥\bot-context C⊥{⋅}C^{\bot}\{\cdot\} and formula BB, we have C⊥{B}≡BC^{\bot}\{B\} \equiv B. We are now showing a more general statement: for any ⊥\bot-context C⊥{⋅}C^{\bot}\{\cdot\}, if ⊢OPALC⊥{A∧B}\vdash_{\mathrm{OPAL}} C^{\bot}\{A \land B\} then ⊢OPALC⊥{A}\vdash_{\mathrm{OPAL}} C^{\bot}\{A\} and ⊢OPALC⊥{B}.Weproceedbyinductiononthederivation\vdash_{\mathrm{OPAL}} C^{\bot}\{B\}. We proceed by induction on the derivation\delta$ of ⊢OPALC⊥{A∧B}\vdash_{\mathrm{OPAL}} C^{\bot}\{A \land B\}. We have the following cases how this derivation can be obtained:

(1):

⊢OPAL⊤⊢OPALC⊥{⊤∧⊤}\frac{\vdash_{\mathrm{OPAL}}\top}{\vdash_{\mathrm{OPAL}} C^{\bot}\{\top\land\top\}}

(2):

⊢OPALA′⊢OPALB′⊢OPALC⊥{A′∧B′}\frac{ \vdash_{\mathrm{OPAL}} A' \qquad \vdash_{\mathrm{OPAL}} B' }{ \vdash_{\mathrm{OPAL}} C^{\bot}\{A' \land B'\} }

(3):

⊢OPALC⊥{A′∧B′}⊢OPALC⊥{A∧B}\frac{ \vdash_{\mathrm{OPAL}} C^{\bot}\{A' \land B'\} }{ \vdash_{\mathrm{OPAL}} C^{\bot}\{A \land B\} }

In Case (1), we have A=B=⊤A = B = \top, and we are done immediately, as δ′\delta' is our desired derivation. In Cases (2) and (3), we apply the induction hypothesis to δ′\delta'. Note that Case (3) subsumes the cases where instead of ≡\equiv, we use one of the rules ww, cc, or ss, as in each case we have that premise and conclusion are equivalent modulo ≡\equiv.

Lemma 6.2. For any formula AA, if ⊢OPAL□A\vdash_{\mathrm{OPAL}} \Box A then also ⊢OPALA\vdash_{\mathrm{OPAL}} A.

Proof. The only rules that have a □\Box as outermost connective in the conclusion are ee, k′k', 4 and 5. We proceed by induction on the derivation δ\delta of ⊢OPAL□A\vdash_{\mathrm{OPAL}} \Box A and the formula AA, and we have the following cases:

1:  e⊤□⊤2:  δ′∥OPAL□A′□□A′3:  δ′∥OPAL◊A′□◊A′4:  □A′δA∥A5:  k′δ′∥OPAL□A′∧□A′′□(A′∧A′′)\begin{aligned} 1:\;&e\frac{\top}{\Box\top} \qquad 2:\;\frac{\delta'\parallel\mathrm{OPAL}}{\frac{\Box A'}{\Box\Box A'}}\qquad 3:\;\frac{\delta'\parallel\mathrm{OPAL}}{\frac{\Diamond A'}{\Box\Diamond A'}}\qquad 4:\;\Box\frac{A'}{\delta_A\parallel A} \qquad 5:\;k'\frac{\delta'\parallel\mathrm{OPAL}}{\Box A' \wedge\Box A'' \over\Box(A'\wedge A'')} \end{aligned}

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 ⊢OPAL□A′\vdash_{\mathrm{OPAL}}\Box A' and ⊢OPAL□A′′\vdash_{\mathrm{OPAL}}\Box A'', to which we apply the induction hypothesis, to obtain ⊢OPALA′\vdash_{\mathrm{OPAL}} A' and ⊢OPALA′′\vdash_{\mathrm{OPAL}} A'', from which we get immediately ⊢OPALA′∧A′′\vdash_{\mathrm{OPAL}} A'\wedge A''.

Definition 6.3. A tame context is a context in which the hole {⋅}\{\cdot\} does not occur inside an ∧\wedge, nor in the scope of a ◊\Diamond or ⟨A⟩\langle A\rangle modality, i.e., a tame context is generated by the grammar

C{⋅}:={⋅}∣A∨C{⋅}∣C{⋅}∨A∣□C{⋅}∣[A]C{⋅}(12)C\{\cdot\}:=\{\cdot\}\mid A\vee C\{\cdot\}\mid C\{\cdot\}\vee A\mid\Box C\{\cdot\}\mid[A]C\{\cdot\} \tag*{(12)}

Lemma 6.4. Let C{⋅}C\{\cdot\} be a tame context and let AA and BB be formulas. Then there is a derivation

C{A}∧C{B}δ∥OPAL C{A∧B}\frac{C\{A\}\wedge C\{B\}}{\delta\parallel\mathrm{OPAL}}\,C\{A\wedge B\}

Proof. We construct δ\delta by induction on C{⋅}C\{\cdot\}. The case of C{⋅}={⋅}C\{\cdot\}=\{\cdot\} is trivial. The cases for C{⋅}=D∨C′{⋅}C\{\cdot\}=D\vee C'\{\cdot\} and C{⋅}=□C′{⋅}C\{\cdot\}=\Box C'\{\cdot\} and C{⋅}=[D]C′{⋅}C\{\cdot\}=[D]C'\{\cdot\} are as follows (respectively):

(D∨C′{A})∧(D∨C′{B})sD∨DC∨C′{A}∧C′{B}δ′∥OPAL C′{A∧B}\frac{(D\vee C'\{A\})\wedge(D\vee C'\{B\})} {s\quad\frac{D\vee D}{C}\vee\frac{C'\{A\}\wedge C'\{B\}}{\delta'\parallel\mathrm{OPAL}}\,C'\{A\wedge B\}}
□C′{A}∧□C′{B}k′□(C′{A}∧C′{B}δ′∥OPAL C′{A∧B})\frac{\Box C'\{A\}\wedge\Box C'\{B\}} {k'\quad\Box\left(\frac{C'\{A\}\wedge C'\{B\}}{\delta'\parallel\mathrm{OPAL}}\,C'\{A\wedge B\}\right)}
[D]C′{A}∧[D]C′{B}k_′[D](C′{A}∧C′{B}δ′∥OPAL C′{A∧B})\frac{[D]C'\{A\}\wedge[D]C'\{B\}} {k'_{\_}\quad[D]\left(\frac{C'\{A\}\wedge C'\{B\}}{\delta'\parallel\mathrm{OPAL}}\,C'\{A\wedge B\}\right)}

where δ′\delta' exists by induction hypothesis, and the case C{⋅}=C′{⋅}∨DC\{\cdot\}=C'\{\cdot\}\vee D is similar to C{⋅}=D∨C′{⋅}C\{\cdot\}=D\vee C'\{\cdot\}.

Lemma 6.5. Let C{⋅}C\{\cdot\} be a tame context and let A1,…,AnA_1,\ldots,A_n be formulas for n≥0n\ge0. Then there is a derivation

C{A1}∧⋯∧C{An}δ∥OPAL C{A1∧⋯∧An}\frac{C\{A_1\}\wedge\cdots\wedge C\{A_n\}}{\delta\parallel\mathrm{OPAL}}\,C\{A_1\wedge\cdots\wedge A_n\}

Proof. We proceed by induction on nn. The base case is n=0n=0. We can show by induction on C{⋅}C\{\cdot\} that there is a derivation from ⊤\top to C{⊤}C\{\top\} via:

⊤≡w⊥D∨⊤δ′∥OPAL C′{⊤}⊤e□⊤□δ′∥OPALC′{⊤}⊤e[⋅][D]⊤δ′∥OPAL C′{⊤}\frac{\top}{\equiv\quad\frac{\mathrm{w}\frac{\bot}{D}\vee\frac{\top}{\delta'\parallel\mathrm{OPAL}}\,C'\{\top\}}{}} \qquad \frac{\top}{e_{\Box}\quad\frac{\top}{\Box\frac{\delta'\parallel\mathrm{OPAL}}{C'\{\top\}}}} \qquad \frac{\top}{e_{[\cdot]}\quad[D]\frac{\top}{\delta'\parallel\mathrm{OPAL}}\,C'\{\top\}}

and the inductive case follows immediately from Lemma 6.4. □

Lemma 6.6. For every HPAL inference rule

G1⋯GnG\frac{G_1 \quad\cdots\quad G_n}{G}

with n≥0n \ge0, there is an OPAL derivation

G1τ∧⋯∧GnτGτ\frac{G_1^\tau\land\cdots\land G_n^\tau}{G^\tau}

Proof. We construct δ\delta for each rule of HPAL. Note that for the axioms (⊤)(\top) and (Ax), as well as for the branching rules (∧)(\land), (◊P)(\Diamond\mathrm{P}), (⟨⋅⟩0)(\langle\cdot\rangle_0), and (⟨⋅⟩1)(\langle\cdot\rangle_1), we make crucial use of Lemma 6.4 and Lemma 6.5. The most involved cases are the rules (◊P)(\Diamond\mathrm{P}) and (Recall), for which we show the derivation δ\delta in Figure 4. For the convenience of the reader, a complete list is shown in Appendix § 11. □

OPAL-derivations for the HPAL rules

Figure 4. OPAL-derivations for the HPAL rules (◊P\Diamond\mathsf{P}) and (Recall)

Theorem 6.7. If ⊢HPALA\vdash_{\mathrm{HPAL}} A then ⊢OPALA\vdash_{\mathrm{OPAL}} A.

Proof. By induction on the HPAL derivation of the hypersequent G=AG = A, we can, by applying Lemma 6.6 at each step, construct an OPAL-derivation with conclusion Gτ=□AG^\tau= \Box A. By Lemma 6.2, this yields ⊢OPALA\vdash_{\mathrm{OPAL}} A. □

Corollary 6.8 (Completeness). If ⊢PALA\vdash_{\mathrm{PAL}} A then ⊢OPALA\vdash_{\mathrm{OPAL}} A.

Proof. Let AA be a formula with ⊢PALA\vdash_{\mathrm{PAL}} A. By Theorem 3.4, we have ⊢HPALA\vdash_{\mathrm{HPAL}} A. Then, by Theorem 6.7, we get ⊢OPALA\vdash_{\mathrm{OPAL}} A. □

Cut Elimination

The general cut rule in deep inference systems is

A∧Aˉ⊥(13)\frac{A \land\bar{A}}{\bot} \tag*{(13)}

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 ⊢OPAL+cutA\vdash_{\mathrm{OPAL+cut}} A then ⊢HPAL+(cut)A\vdash_{\mathrm{HPAL+(cut)}} A.

This is enough to prove cut admissibility for OPAL:

Corollary 7.2. If ⊢OPAL+cutA\vdash_{\mathrm{OPAL+cut}} A then ⊢OPALA\vdash_{\mathrm{OPAL}} A.

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 k′k'-rule, which would be considered an up-rule in the system for S4, presented in [52]. Furthermore, Stouppa’s system uses the rules

t′ □AA4′ ⋄⋄A⋄A5′ ⋄□A□A(14)\mathrm{t'}\ \frac{\square A}{A} \qquad \mathrm{4'}\ \frac{\diamond\diamond A}{\diamond A} \qquad \mathrm{5'}\ \frac{\diamond\square A}{\square A} \tag*{(14)}

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 A={a,b,…}\mathcal{A} = \{a, b, \ldots\} of agents, and each agent has its own pair of modalities □a\square_a and ⋄a\diamond_a. The inference rules are very easy to adjust (simply replace □\square and ⋄\diamond in each rule in Figure 2 by □a\square_a and ⋄a\diamond_a, 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 E=⟨E,∼,pre⁡⟩\mathcal{E} = \langle E, \sim, \operatorname{pre}\rangle, where E={e,f,…}E = \{e, f, \ldots\} is a finite set of epistemic actions that may be indistinguishable from the agents’ perspective, written as e∼fe \sim f, and that can be executed only when their precondition is satisfied, i.e. when we have M,w⊩pre⁡(e)M, w \Vdash\operatorname{pre}(e). This logic generalises PAL, as a public announcement [A][A] can be represented by a model of only a single action {e}\{e\} with pre⁡(e)=A\operatorname{pre}(e) = A. The reduction axioms are similar to those of PAL but the one for the epistemic modality now becomes [e]□B⇔(pre⁡(e)→⋀e∼f[f]B)[e]\square B \Leftrightarrow(\operatorname{pre}(e) \rightarrow\bigwedge_{e\sim f}[f]B). 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 A→BA \to B does not imply the validity of [A]C→[B]C[A]C \to[B]C. However, if A↔BA \leftrightarrow B, then also [A]C↔[B]C[A]C \leftrightarrow[B]C.

This means that we could add the inference rule

[A]C[B]C\frac{[A]C}{[B]C}

with the proviso that we have A↔BA \leftrightarrow B. 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 A→BA \to B is a theorem then there is CC in the common vocabulary such that both A→CA \to C and C→BC \to B 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 CC of A→BA \to B provides an explanation of the truth of A→BA \to B, then one would expect such an explanation to be expressed in the same language as A→BA \to B. In particular, announcements [α][\alpha] should appear in the interpolant if [α][\alpha] occurs in both AA and BB. 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 AA. When A=pA=p is an atom, we simply use the atomic identity rule ai. The other cases are handled with the following derivations.

⊤B‾∨B i⊤C‾∨C i(B‾∨C‾)∨(B∧C) s\frac{\dfrac{\top}{\overline{B}\vee B}\ i \qquad\dfrac{\top}{\overline{C}\vee C}\ i}{(\overline{B}\vee\overline{C})\vee(B\wedge C)}\ s
⊤⊤B‾∨B □i⋄B‾∨□B e[⋅]\frac{\top}{\dfrac{\top}{\overline{B}\vee B}\ \Box i\qquad\diamond\overline{B}\vee\Box B}\ e_{[\cdot]}
⊤⊤C‾∨C [B]i⟨B⟩C‾∨[B]C k[⋅]\frac{\top}{\dfrac{\top}{\overline{C}\vee C}\ [B]i\qquad\langle B\rangle\overline{C}\vee[B]C}\ k_{[\cdot]}

For m□m_{\Box}, m4□m_{4}^{\Box}, m5□m_{5}^{\Box}, s∗s^{*} and m[⋅]∗m^{*}_{[\cdot]}, we use the following derivations.

⊤A≡⊥A∨⊥B‾≡⊥⊥A‾∨B≡□(A∨B) c\frac{ \dfrac{\top}{A}\equiv \qquad \dfrac{\perp}{A\vee\frac{\perp}{\overline{B}}}\equiv \qquad \dfrac{\perp}{\frac{\perp}{\overline{A}}\vee B}\equiv }{ \Box(A\vee B) }\ c
□B∨□A□□A 4□(B∨□A) m□\frac{\Box B\vee \dfrac{\Box A}{\Box\Box A}\ 4}{\Box(B\vee\Box A)}\ m_{\Box}
□B∨⋄A□⋄A 5□(B∨⋄A) m□\frac{\Box B\vee \dfrac{\diamond A}{\Box\diamond A}\ 5}{\Box(B\vee\diamond A)}\ m_{\Box}
□C∨⋄B□(A∨⋄B)□A∨⋄B□(A∨⋄B)\frac{\Box C\vee\diamond B}{\Box(A\vee\diamond B)}\quad \frac{\Box A\vee\diamond B}{\Box(A\vee\diamond B)}
□A∨⋄B□(A∨⋄B)□C∨⋄B□(A∨⋄B)\frac{\Box A\vee\diamond B}{\Box(A\vee\diamond B)}\quad \frac{\Box C\vee\diamond B}{\Box(A\vee\diamond B)}
□A∨□(C∨B)□C∨□B k□A∨⋄B□(A∨⋄B) m□5∨□C\frac{ \Box A\vee \frac{\Box(C\vee B)}{\Box C\vee\Box B}\ k }{ \frac{\Box A\vee\diamond B}{\Box(A\vee\diamond B)}\ m_{\Box}^{5} \vee\Box C }
\frac{ [\alpha] \frac{\equiv\frac{B}{B\vee\frac{\perp}{\mathsf{w}\,\overline{C}}}\vee[\alpha]\frac{\equiv\frac{C}{\frac{\perp}{\mathsf{w}\,\overline{B}}\vee C}}}{[\alpha](B\vee C)} }\ c

Finally, for k[⋅]∗k^{*}_{[\cdot]}, k⟨⋅⟩∗k^{*}_{\langle\cdot\rangle}, p⋄∗p^{*}_{\diamond} and p□∗p^{*}_{\Box}, we proceed by induction on α\alpha. The case where α\alpha is empty is trivial. For the inductive case, where α=α′⋅A\alpha=\alpha'\cdot A, we use the induction hypothesis and the corresponding rules k[⋅]k_{[\cdot]}, k⟨⋅⟩k_{\langle\cdot\rangle}, p⋄p_{\diamond} and p□p_{\Box}. This is straightforward. □\square

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 δ\delta from AA to BB in OPAL then there is a proof π\pi of A→BA\to B in HPAL. To do so, we first show that all inference rules of OPAL are sound.

Lemma 5.1. For every rule ρ\rho of OPAL, we have ⊢PALA→B\vdash_{\mathrm{PAL}} A\to B and ⊢HPALA,B‾\vdash_{\mathrm{HPAL}} A,\overline{B}.

Proof. We show that, for each rule ρ AB\rho\ \frac{A}{B} in OPAL there is an HPAL derivation of Aˉ,B\bar{A}, B. We consider here the dynamic rules (as for propositional and modal rules, this is straightforward). We show ⊢HPALAˉ,B\vdash_{\mathrm{HPAL}}\bar{A}, B by means of the following derivations, where every πi\pi_i exists by Lemma 3.2.

  • For e[⋅]\mathrm{e}_{[\cdot]} we have the three following derivations, depending on whether atomatom is a (negated) atom or unit:

e[⋅] p[A]p⇝p,pˉ,Aˉ //A p (Ax)pˉ,Aˉ //A ppˉ,[A]p ([⋅]0) (Atom)⊤,⊥,Aˉ //A ⊤ (T)⊥,Aˉ //A ⊤⊥,[A]⊤ ([⋅]0) (Atom)⊤,[A]⊥⊤,[A]⊥ (T)\mathrm{e}_{[\cdot]}\ \frac{p}{[A]p} \quad\leadsto\quad \frac{\frac{}{p,\bar{p},\bar{A}\ //_{A}\ p}\ (\mathrm{Ax})}{\frac{\bar{p},\bar{A}\ //_{A}\ p}{\bar{p},[A]p}\ ([\cdot]_0)\ (\mathrm{Atom})} \quad \frac{\frac{}{ \top,\bot,\bar{A}\ //_{A}\ \top}\ (\mathrm{T})}{\frac{\bot,\bar{A}\ //_{A}\ \top}{\bot,[A]\top}\ ([\cdot]_0)\ (\mathrm{Atom})} \quad \frac{\top,[A]\bot}{\top,[A]\bot}\ (\mathrm{T})
  • For k[⋅]\mathrm{k}_{[\cdot]} we have:

\mathrm{k}_{[\cdot]}\ \frac{[A](B\lor C)}{[A]B\lor\langle A\rangle C} \quad\leadsto\quad \frac{ \frac{ \frac{ \pi_3\ \frac{\bar{A}\ //_{A}\ B,C,\bar{B}} {\bar{A}\ //_{A}\ B,C,\bar{B}\land\bar{C}}\ (\land) \qquad \pi_4\ \frac{\bar{A}\ //_{A}\ B,C,\bar{C}} {\bar{A}\ //_{A}\ B,C,\bar{B}\land\bar{C}}\ (\land) }{ \bar{A}\ //_{A}\ B,C,\bar{B}\land\bar{C} }\ (\langle\cdot\rangle_1) }{ \frac{\bar{A},\langle A\rangle(\bar{B}\land\bar{C})\ //_{A}\ B,C}{} } \quad \frac{\pi_2\ \frac{\bar{A}\ //_{A}\ B,C}{\bar{A},\langle A\rangle(\bar{B}\land\bar{C})\ //_{A}\ B,C}\ (\langle\cdot\rangle_1)} { \frac{\bar{A},\langle A\rangle(\bar{B}\land\bar{C}),\langle A\rangle C\ //_{A}\ B}{} } \quad \frac{\langle A\rangle(\bar{B}\land\bar{C}),[A]B,\langle A\rangle C}{\langle A\rangle(\bar{B}\land\bar{C}),[A]B\lor\langle A\rangle C}\ ([\cdot]_0)}
  • For k[⋅]′\mathrm{k}'_{[\cdot]} we have:

\mathrm{k}'_{[\cdot]}\ \frac{[A]B\land[A]C}{[A](B\land C)} \quad\leadsto\quad \frac{ \frac{ \frac{ \pi_3\ \frac{\bar{A}\ //_{A}\ B,\bar{B},\bar{C}} {\bar{A}\ //_{A}\ B\land C,\bar{B},\bar{C}}\ (\land) \qquad \pi_4\ \frac{\bar{A}\ //_{A}\ C,\bar{B},\bar{C}} {\bar{A}\ //_{A}\ B\land C,\bar{B},\bar{C}}\ (\land) }{ \bar{A}\ //_{A}\ B\land C,\bar{B},\bar{C} }\ (\langle\cdot\rangle_1) }{ \bar{A},\langle A\rangle\bar{C}\ //_{A}\ B\land C,\bar{B} } \quad \frac{\pi_2\ \frac{\bar{A}\ //_{A}\ B\land C,\bar{B}} {\bar{A},\langle A\rangle\bar{C}\ //_{A}\ B\land C,\bar{B}}\ (\langle\cdot\rangle_1) }{ \bar{A},\langle A\rangle\bar{B},\langle A\rangle\bar{C}\ //_{A}\ B\land C } \quad \frac{\langle A\rangle\bar{B},\langle A\rangle\bar{C},[A](B\land C)} {\langle A\rangle\bar{B}\lor\langle A\rangle\bar{C},[A](B\land C)}\ ([\cdot]_0)}
  • For k⟨⋅⟩\mathrm{k}_{\langle\cdot\rangle} we have:

k⟨⋅⟩ ⟨A⟩B[A]B⇝π1 Aˉ,Aˉ //A B,BˉAˉ,[A]B //A Bˉ ([⋅]1)Aˉ,[A]B //A Bˉ ([⋅]0)[A]Bˉ,[A]B\mathrm{k}_{\langle\cdot\rangle}\ \frac{\langle A\rangle B}{[A]B} \quad\leadsto\quad \frac{ \frac{ \frac{\pi_1\ \frac{\bar{A},\bar{A}\ //_{A}\ B,\bar{B}}{} }{\bar{A},[A]B\ //_{A}\ \bar{B}} \ ([\cdot]_1) }{ \frac{\bar{A},[A]B\ //_{A}\ \bar{B}}{} }\ ([\cdot]_0) }{ [A]\bar{B},[A]B }
  • For p⋄p_{\diamond} we have:

p⋄⋄⟨A⟩B[A]⋄B⇝π1⟨⋄5⟩A‾//⋄B∣A‾//B,B‾A‾//⋄B∣A‾ B‾(⌈⋅⌉0)A‾//⋄B∣[A]B‾A‾,□[A]B‾//⋄B□[A]B‾,[A]⋄Bp_{\diamond}\frac{\diamond\langle A\rangle B}{[A]\diamond B}\leadsto \begin{array}{c} \pi_{1}\\ \frac{\langle\diamond5\rangle\frac{\overline{A}\mathbin{//}\diamond B\mid\overline{A}\mathbin{//}B,\overline{B}}{\overline{A}\mathbin{//}\diamond B\mid\overline{A}\,\overline{B}}} {(\lceil\cdot\rceil_{0})\frac{\overline{A}\mathbin{//}\diamond B\mid[A]\overline{B}}{\overline{A},\square[A]\overline{B}\mathbin{//}\diamond B}} \\ \frac{\square[A]\overline{B},[A]\diamond B}{} \end{array}
  • For p□p_{\square} we have:

p□□[A]B[A]□B⇝π1π2(⟨∨⟩1)A‾,⋄⟨A⟩B‾,//A,A‾//BA‾,⋄⟨A⟩B‾,//A∣A‾//BA‾,⋄⟨A⟩B‾,//A∣A‾//B,B‾A‾,⋄⟨A⟩B‾,//A∣A‾//B(⟨⋄5⟩)A‾,⋄⟨A⟩B‾,//A∣⟨A⟩B‾,A‾//B(New)+(Recall)A‾,⋄⟨A⟩B‾,//A∣A‾//B(□)A‾,⋄⟨A⟩B‾,//A∣//AB(⌈⋅⌉0)A‾,⋄⟨A⟩B‾,//A∣⋄B⋄⟨A⟩B‾,[A]□Bp_{\square}\frac{\square[A]B}{[A]\square B}\leadsto \begin{array}{c} \pi_{1}\qquad\pi_{2}\\ (\langle\vee\rangle_{1})\frac{\overline{A},\diamond\langle A\rangle\overline{B},\mathbin{//}A,\overline{A}\mathbin{//}B} {\overline{A},\diamond\langle A\rangle\overline{B},\mathbin{//}A\mid\overline{A}\mathbin{//}B} \qquad \frac{\overline{A},\diamond\langle A\rangle\overline{B},\mathbin{//}A\mid\overline{A}\mathbin{//}B,\overline{B}} {\overline{A},\diamond\langle A\rangle\overline{B},\mathbin{//}A\mid\overline{A}\mathbin{//}B} \\ (\langle\diamond5\rangle)\frac{\overline{A},\diamond\langle A\rangle\overline{B},\mathbin{//}A\mid\langle A\rangle\overline{B},\overline{A}\mathbin{//}B}{} \\ (\mathrm{New})+(\mathrm{Recall})\frac{\overline{A},\diamond\langle A\rangle\overline{B},\mathbin{//}A\mid\overline{A}\mathbin{//}B}{} \\ (\square)\frac{\overline{A},\diamond\langle A\rangle\overline{B},\mathbin{//}A\mid\mathbin{//}A B}{} \\ (\lceil\cdot\rceil_{0})\frac{\overline{A},\diamond\langle A\rangle\overline{B},\mathbin{//}A\mid\diamond B}{\diamond\langle A\rangle\overline{B},[A]\square B} \end{array}
  • For rr we have:

rA∧[A]B⟨A⟩B⇝π1π2π3(⟨∨⟩0)A,A‾,⟨A⟩BA‾,⟨A⟩B//B‾A,A‾//A∣A‾,B‾,BA‾,⟨A⟩B//B‾(⟨∨⟩0)A,A‾,⟨A⟩BA‾,⟨A⟩B‾,⟨A⟩B(∨)A‾,⟨A⟩B‾,⟨A⟩BA‾∨⟨A⟩B‾,⟨A⟩Br\frac{A\land[A]B}{\langle A\rangle B}\leadsto \begin{array}{c} \pi_{1}\qquad\pi_{2}\qquad\pi_{3}\\ (\langle\vee\rangle_{0})\frac{A,\overline{A},\langle A\rangle B}{\overline{A},\langle A\rangle B\mathbin{//}\overline{B}} \qquad \frac{A,\overline{A}\mathbin{//}A\mid\overline{A},\overline{B},B}{\overline{A},\langle A\rangle B\mathbin{//}\overline{B}} \\ (\langle\vee\rangle_{0})\frac{A,\overline{A},\langle A\rangle B}{\overline{A},\langle A\rangle\overline{B},\langle A\rangle B} \\ (\vee)\frac{\overline{A},\langle A\rangle\overline{B},\langle A\rangle B}{\overline{A}\vee\langle A\rangle\overline{B},\langle A\rangle B} \end{array}
  • For nn we have:

nA‾[A]B⇝π1(⌈⋅⌉0)A,A‾//BA,[A]Bn\frac{\overline{A}}{[A]B}\leadsto \begin{array}{c} \pi_{1}\\ (\lceil\cdot\rceil_{0})\frac{A,\overline{A}\mathbin{//}B}{A,[A]B} \end{array}

□\square

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.

(w)G∣X//ΓG∣X//Γ,A(ew)G∣XG∣X∣Y(\mathrm{w})\frac{\mathcal{G}\mid X\mathbin{//}\Gamma}{\mathcal{G}\mid X\mathbin{//}\Gamma,A} \qquad (\mathrm{ew})\frac{\mathcal{G}\mid X}{\mathcal{G}\mid X\mid Y}

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 CC be a formula and XX be a dynamic hypersequent. The dynamic sequent X↑CX^{\uparrow C} is obtained by replacing all indices α\alpha occurring in XX by C⋅αC \cdot\alpha. In particular, if X=//α1Γ1//⋯//αnΓnX = \mathbin{//}_{\alpha_1}\Gamma_1 \mathbin{//}\cdots\mathbin{//}_{\alpha_n}\Gamma_n, the resulting dynamic sequent is X↑C:=//C⋅α1Γ1//⋯//C⋅αnΓnX^{\uparrow C} := \mathbin{//}_{C\cdot\alpha_1}\Gamma_1 \mathbin{//}\cdots\mathbin{//}_{C\cdot\alpha_n}\Gamma_n. If G=X1∣⋯∣XkG = X_1 \mid\cdots\mid X_k, the dynamic hypersequent G↑CG^{\uparrow C} is obtained by lifting all dynamic sequents XiX_i occurring in it, i.e., G↑C:=X1↑C∣⋯∣Xk↑CG^{\uparrow C} := X_1^{\uparrow C}\mid\cdots\mid X_k^{\uparrow C}. Now, the lift rule is:

GG↑C  (lift)(15)\frac{G}{G^{\uparrow C}}\;(\mathrm{lift}) \tag*{(15)}

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 GG is an axiom, then so is G↑CG^{\uparrow C}. Otherwise, we consider the last applied rule (R)(\mathcal{R}) in the derivation: we apply the induction hypothesis to the premise(s) of (R)(\mathcal{R}) and then apply (R)(\mathcal{R}) again. This is straightforward. For the sake of clarity, the case where the last rule is an instance of ([⋅]0)([\cdot]0) is provided below.

G∣X//αA,Γ∣//α⋅ABG∣X//α[A]B,Γ  ([⋅]0)⟹(IH)G↑C∣X↑C//C⋅αA,Γ∣//C⋅α⋅ABG↑C∣X↑C//C⋅α[A]B,Γ  ([⋅]0)\begin{array}{c} \frac{G\mid X\mathbin{//}_{\alpha}A,\Gamma\mid\mathbin{//}_{\alpha\cdot A}B}{G\mid X\mathbin{//}_{\alpha}[A]B,\Gamma}\;([\cdot]0) \qquad \overset{\mathrm{(IH)}}{\Longrightarrow} \qquad \frac{G^{\uparrow C}\mid X^{\uparrow C}\mathbin{//}_{C\cdot\alpha}A,\Gamma\mid\mathbin{//}_{C\cdot\alpha\cdot A}B}{G^{\uparrow C}\mid X^{\uparrow C}\mathbin{//}_{C\cdot\alpha}[A]B,\Gamma}\;([\cdot]0) \end{array}

The other cases are similar. □\square

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 [C]δ[C]\delta of [C]A[C]A from a derivation δ\delta of AA, 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 δ\delta ABOPAL\dfrac{A}{B}_{\mathsf{OPAL}}, we have ⊢PALA→B\vdash_{\mathsf{PAL}} A\to B and ⊢HPAL+(cut)A‾,B\vdash_{\mathsf{HPAL}+\mathrm{(cut)}}\overline{A},B.

Proof. Let δ\delta ABOPAL\dfrac{A}{B}_{\mathsf{OPAL}} be a derivation from AA to BB in OPAL. In the following we show that ⊢HPAL+(cut)A‾,B\vdash_{\mathsf{HPAL}+\mathrm{(cut)}}\overline{A},B (we then get ⊢HPAL+(cut)A‾∨B\vdash_{\mathsf{HPAL}+\mathrm{(cut)}}\overline{A}\lor B by applying (∨)(\lor), and ⊢PALA→B\vdash_{\mathsf{PAL}} A\to B follows from Corollary 3.6 and Theorem 3.4).

We proceed by induction on the derivation δ\delta, and we have the following cases:

(i) If δ\delta is a formula, then δ=A\delta=A and ⊢HPALA‾,A\vdash_{\mathsf{HPAL}}\overline{A},A by Lemma 3.2.

(ii) Suppose δ=AθB⊛CξD\delta= \begin{array}{c} A\\ \theta\\ B \end{array} \mathbin{\circledast} \begin{array}{c} C\\ \xi\\ D \end{array} where ⊛∈{∧,∨}\circledast\in\{\land,\lor\}. We only show the case where ⊛=∧\circledast= \land (the case of ∨\lor is treated similarly), for which we need to show ⊢HPALAˉ∨Cˉ,B∧D\vdash_{\mathrm{HPAL}} \bar{A} \lor\bar{C}, B \land D. By induction hypothesis ⊢HPALAˉ,B\vdash_{\mathrm{HPAL}} \bar{A}, B and ⊢HPALCˉ,D\vdash_{\mathrm{HPAL}} \bar{C}, D. By Lemma B.1 we can use weakening, and obtain the desired result by the following derivation.

π1Aˉ,Bπ2Cˉ,DAˉ,Cˉ,BAˉ,Cˉ,DAˉ,Cˉ,B∧D  (∧)Aˉ,Cˉ,B∧DAˉ∨Cˉ,B∧D  (∨)\begin{aligned} &\frac{\pi_1}{\bar{A},B}\quad\frac{\pi_2}{\bar{C},D}\\ &\frac{\bar{A},\bar{C},B\qquad\bar{A},\bar{C},D}{\bar{A},\bar{C},B\land D}\;(\land)\\ &\frac{\bar{A},\bar{C},B\land D}{\bar{A}\lor\bar{C},B\land D}\;(\lor) \end{aligned}

(iii) Suppose δ=◯AθB\delta= \bigcirc\begin{array}{c} A\\ \theta\\ B \end{array} where ◯∈{□,⋄,[C],⟨C⟩}\bigcirc\in\{\Box,\diamond,[C],\langle C\rangle\}. We first show the case where ◯=□\bigcirc= \Box and then the case where ◯=[C]\bigcirc= [C] (those with ⋄\diamond and ⟨C⟩\langle C\rangle are treated similarly).

If δ=□AθB\delta= \Box\begin{array}{c} A\\ \theta\\ B \end{array}, we need to show ⊢HPAL⋄Aˉ,□B\vdash_{\mathrm{HPAL}} \diamond\bar{A},\Box B. By induction hypothesis ⊢HPALAˉ,B\vdash_{\mathrm{HPAL}} \bar{A},B. By Lemma B.1 we can use external weakening, and obtain the desired result by the following derivation.

πAˉ,BAˉ,B⋄Aˉ∣Aˉ,B  (ew)⋄Aˉ∣Aˉ,B⋄Aˉ∣B  (⋄5)⋄Aˉ∣B⋄Aˉ,□B  (□⋄)\begin{aligned} &\frac{\pi}{\bar{A},B}\\ &\frac{\bar{A},B}{\diamond\bar{A}\mid\bar{A},B}\;(\mathrm{ew})\\ &\frac{\diamond\bar{A}\mid\bar{A},B}{\diamond\bar{A}\mid B}\;(\diamond5)\\ &\frac{\diamond\bar{A}\mid B}{\diamond\bar{A},\Box B}\;(\Box\diamond) \end{aligned}

If δ=[C]AθB\delta= [C]\begin{array}{c} A\\ \theta\\ B \end{array}, we need to show ⊢HPAL⟨C⟩Aˉ,[C]B\vdash_{\mathrm{HPAL}} \langle C\rangle\bar{A},[C]B. By induction hypothesis ⊢HPALAˉ,B\vdash_{\mathrm{HPAL}} \bar{A},B. Here we use Lemma B.2 together with Lemma B.1 and reach the desired result by the following derivation, where π1\pi_1 exists by Lemma 3.2 and $\pi_2 exists by induction hypothesis.

π1π2C,Cˉ//CBAˉ,BCˉ,⟨C⟩Aˉ//CB⟨C⟩Aˉ,[C]B\begin{gathered} \pi_1 \qquad\pi_2\\ C,\bar C \mathbin{//}_{C} B \qquad\bar A,B\\ \frac{\bar C,\langle C\rangle\bar A \mathbin{//}_{C} B}{\langle C\rangle\bar A,[C]B} \end{gathered}

(iv) Finally, suppose δ=ρAθ//BCζ//D\delta=\rho\begin{array}{c} A\\ \theta\mathbin{//}B\\ \hline C\\ \zeta\mathbin{//}D \end{array} where ρBC\rho\begin{array}{c} B\\ \hline C \end{array} is an instance of an inference rule.

We need to show ⊢HPALAˉ,D\vdash_{\mathrm{HPAL}}\bar A,D. By induction hypothesis we have ⊢HPALAˉ,B\vdash_{\mathrm{HPAL}}\bar A,B and ⊢HPALCˉ,D\vdash_{\mathrm{HPAL}}\bar C,D. Moreover, by Lemma 5.1 we have ⊢HPALBˉ,C\vdash_{\mathrm{HPAL}}\bar B,C. By Theorem 3.5 we can use (cut) twice to obtain the desired conclusion as follows:

Aˉ,BBˉ,CCˉ,DBˉ,D (cut)Aˉ,D (cut)\frac{\bar A,B \qquad\frac{\bar B,C \qquad\bar C,D}{\bar B,D}\text{ (cut)}}{\bar A,D}\text{ (cut)}

Missing proof for Section 6

Lemma 6.6. For every HPAL inference rule

(Rule) G1⋯GnG(16)\text{(Rule)}\ \frac{G_1\quad\cdots\quad G_n}{G} \tag*{(16)}

with n≥0n\ge0, there is an OPAL derivation

G1τ∧⋯∧GnτGτ δ//OPAL\frac{G_1^\tau\land\cdots\land G_n^\tau}{G^\tau}\ \delta\mathbin{//}_{\mathrm{OPAL}}

Proof. We construct δ\delta for each rule of HPAL.

  • For (T), we use for δ\delta the base case of Lemma 6.5.

  • For (Ax), we have δ\delta as follows:

(Ax)G∣X//αΓ,pˉ,p⇝Gτ∨□(Xτ∨[α](Γτ∨ai ⊤pˉ∨p))\text{(Ax)}\quad\frac{\mathcal{G}\mid X\mathbin{//}_{\alpha}\Gamma,\bar{p},p}{} \leadsto \mathcal{G}^{\tau}\vee\Box\left(X^{\tau}\vee[\alpha]\left(\Gamma^{\tau}\vee\mathrm{ai}\ \frac{\top}{\bar{p}\vee p}\right)\right)

where δ′\delta' is again the base case of the proof of Lemma 6.5.

  • For (∨)(\vee), δ\delta is the identity derivation:

(∨)G∣X//αΓ,A,BG∣X//αΓ,A∨B⇝Gτ∨□(Xτ∨[α](Γτ∨(A∨B)))\text{(}\vee\text{)}\quad \frac{\mathcal{G}\mid X\mathbin{//}_{\alpha}\Gamma,A,B} {\mathcal{G}\mid X\mathbin{//}_{\alpha}\Gamma,A\vee B} \leadsto \mathcal{G}^{\tau}\vee\Box\left(X^{\tau}\vee[\alpha]\left(\Gamma^{\tau}\vee(A\vee B)\right)\right)
  • For (∧)(\wedge), δ\delta directly obtained from Lemma 6.4:

(∧)G∣X//αΓ,AG∣X//αΓ,BG∣X//αΓ,A∧B⇝Gτ∨□(Xτ∨[α](Γτ∨A))∧Gτ∨□(Xτ∨[α](Γτ∨B))\text{(}\wedge\text{)}\quad \frac{\mathcal{G}\mid X\mathbin{//}_{\alpha}\Gamma,A\qquad\mathcal{G}\mid X\mathbin{//}_{\alpha}\Gamma,B} {\mathcal{G}\mid X\mathbin{//}_{\alpha}\Gamma,A\wedge B} \leadsto \mathcal{G}^{\tau}\vee\Box\left(X^{\tau}\vee[\alpha](\Gamma^{\tau}\vee A)\right)\wedge\mathcal{G}^{\tau}\vee\Box\left(X^{\tau}\vee[\alpha](\Gamma^{\tau}\vee B)\right)
Gτ∨□(Xτ∨[α](Γτ∨(A∧B)))\mathcal{G}^{\tau}\vee\Box\left(X^{\tau}\vee[\alpha]\left(\Gamma^{\tau}\vee(A\wedge B)\right)\right)
  • For (□)(\Box) we have

(□)G∣X//αΓ∣//αAG∣X//αΓ,□A⇝Gτ∨□(Xτ∨(□(Xτ∨[α]Γτ)∨□[α]A[α]Γτ∨p□∗□[α]A[α]□A))\text{(}\Box\text{)}\quad \frac{\mathcal{G}\mid X\mathbin{//}_{\alpha}\Gamma\mid\mathbin{//}_{\alpha}A} {\mathcal{G}\mid X\mathbin{//}_{\alpha}\Gamma,\Box A} \leadsto \mathcal{G}^{\tau}\vee \Box\left( X^{\tau}\vee \left( \frac{\Box(X^{\tau}\vee[\alpha]\Gamma^{\tau})\vee\Box[\alpha]A} {[\alpha]\Gamma^{\tau}\vee p_{\Box}^{*}\frac{\Box[\alpha]A}{[\alpha]\Box A}} \right) \right)
  • For (◊⊤)(\Diamond\top), we have

(◊⊤)G∣X//αΓ,◊A,AG∣X//αΓ,◊A⇝Gτ∨□(Xτ∨[α](Γτ∨(◊A∨tA◊A)))\text{(}\Diamond\top\text{)}\quad \frac{\mathcal{G}\mid X\mathbin{//}_{\alpha}\Gamma,\Diamond A,A} {\mathcal{G}\mid X\mathbin{//}_{\alpha}\Gamma,\Diamond A} \leadsto \mathcal{G}^{\tau}\vee\Box\left(X^{\tau}\vee[\alpha]\left(\Gamma^{\tau}\vee\left(\Diamond A\vee\mathrm{t}\frac{A}{\Diamond A}\right)\right)\right)
  • For (◊5)(\Diamond5) G∣X//αΓ,◊A∣Y//αΔ,AG∣X//αΓ,◊A∣Y//αΔ\frac{\mathcal{G}\mid X\mathbin{//}_{\alpha}\Gamma,\Diamond A\mid Y\mathbin{//}_{\alpha}\Delta,A}{\mathcal{G}\mid X\mathbin{//}_{\alpha}\Gamma,\Diamond A\mid Y\mathbin{//}_{\alpha}\Delta} we have

Gτ∨□(Xτ∨([α](Γτ∨◊A)∨p◊∗◊⟨α⟩A[α]◊A))∨□(Yτ∨[α]Δτ)\mathcal{G}^{\tau}\vee \Box\left( X^{\tau}\vee \left( [\alpha](\Gamma^{\tau}\vee\Diamond A)\vee p_{\Diamond}^{*}\frac{\Diamond\langle\alpha\rangle A}{[\alpha]\Diamond A} \right) \right) \vee\Box\left(Y^{\tau}\vee[\alpha]\Delta^{\tau}\right)
Gτ∨□(Xτ∨m[⋅]∗[α](Γτ∨◊A)∨p◊∗◊⟨α⟩A[α]◊A[α](Γτ∨c◊A∨◊A◊A))\mathcal{G}^{\tau}\vee \Box\left( X^{\tau}\vee m_{[\cdot]}^{*} \frac{[\alpha](\Gamma^{\tau}\vee\Diamond A)\vee p_{\Diamond}^{*}\frac{\Diamond\langle\alpha\rangle A}{[\alpha]\Diamond A}} {[\alpha]\left(\Gamma^{\tau}\vee c\frac{\Diamond A\vee\Diamond A}{\Diamond A}\right)} \right)

– For (◊P)(\Diamond P)

G′∣Y//αΔ,B1G′∣Y//αΔ//α⋅B1B2G′∣Y//αΔ//α⋅B1⋅B2B3⋯G′∣Y//αΔ//α⋅βAG∣X//α⋅βΓ,◊A∣Y//αΔ\frac{G' \mid Y \mathbin{//_{\alpha}} \Delta, B_1 \qquad G' \mid Y \mathbin{//_{\alpha}} \Delta\mathbin{//_{\alpha\cdot B_1} } B_2 \qquad G' \mid Y \mathbin{//_{\alpha}} \Delta\mathbin{//_{\alpha\cdot B_1\cdot B_2} } B_3 \qquad\cdots\qquad G' \mid Y \mathbin{//_{\alpha}} \Delta\mathbin{//_{\alpha\cdot\beta} } A} {G \mid X \mathbin{//_{\alpha\cdot\beta}} \Gamma,\Diamond A \mid Y \mathbin{//_{\alpha}} \Delta}

we have

G∨□(Yτ∨[α](Δτ∨B1))∧(G∨□(Yτ∨m[⋅]∗[α]Δτ∨[α⋅B1]B2[α](Δτ∨[B1]B2)))∧⋯∧(G∨□(Yτ∨m[⋅]∗[α]Δτ∨[α⋅β]A[α](Δτ∨[β]A)))≡Gτ∨□(Xτ∨[α⋅β](Γτ∨◊A))∨□(Yτ∨k[⋅]∗[α](Δτ∨⟨β⟩A)[α]Δτ∨⟨α⋅β⟩A)□(Xτ∨m[⋅]∗[α⋅β](Γτ∨◊A)∨p◊∗◊⟨α⋅β⟩A[α⋅β]◊A[α⋅β](Γτ∨c◊A∨◊A◊A))∨□(Yτ∨[α]Δτ)\begin{aligned} &G \lor\Box\left(Y^\tau\lor[\alpha]\left(\Delta^\tau\lor B_1\right)\right) \land \left( G \lor\Box\left( Y^\tau\lor \mathrm{m}^{*}_{[\cdot]} \frac{[\alpha]\Delta^\tau\lor[\alpha\cdot B_1]B_2} {[\alpha](\Delta^\tau\lor[B_1]B_2)} \right) \right) \land\cdots\land \left( G \lor\Box\left( Y^\tau\lor \mathrm{m}^{*}_{[\cdot]} \frac{[\alpha]\Delta^\tau\lor[\alpha\cdot\beta]A} {[\alpha](\Delta^\tau\lor[\beta]A)} \right) \right) \\ &\equiv G^\tau\lor \frac{ \Box\left(X^\tau\lor[\alpha\cdot\beta](\Gamma^\tau\lor\Diamond A)\right) \lor \Box\left( Y^\tau\lor \mathrm{k}^{*}_{[\cdot]} \frac{[\alpha](\Delta^\tau\lor\langle\beta\rangle A)} {[\alpha]\Delta^\tau\lor\langle\alpha\cdot\beta\rangle A} \right) }{ \Box\left( X^\tau\lor \mathrm{m}^{*}_{[\cdot]} \frac{ [\alpha\cdot\beta](\Gamma^\tau\lor\Diamond A) \lor \mathrm{p}^{*}_{\Diamond} \frac{\Diamond\langle\alpha\cdot\beta\rangle A} {[\alpha\cdot\beta]\Diamond A} }{ [\alpha\cdot\beta]\left(\Gamma^\tau\lor c\frac{\Diamond A\lor\Diamond A}{\Diamond A}\right) } \right) \lor \Box\left(Y^\tau\lor[\alpha]\Delta^\tau\right) } \end{aligned}

where G=(G′)τ=(G∣X//α⋅βΓ,◊A)τ=Gτ∨□(Xτ∨[α⋅β](Γτ∨◊A))G=(G')^\tau=(G\mid X\mathbin{//_{\alpha\cdot\beta}}\Gamma,\Diamond A)^\tau=G^\tau\lor\Box(X^\tau\lor[\alpha\cdot\beta](\Gamma^\tau\lor\Diamond A)), and δ1\delta_1 is obtained from Lemma 6.5, and δ0\delta_0 is the derivation

B1∧[B1]B2∧[B1⋅B2]B3∧⋯∧[B1⋅B2⋯Bn]AB1∧[B1](B2∧[B2](B3∧⋯[Bn−1](Bn∧[Bn]A)⋯ ))\frac{ B_1\land[B_1]B_2\land[B_1\cdot B_2]B_3\land\cdots\land[B_1\cdot B_2\cdots B_n]A }{ B_1\land[B_1](B_2\land[B_2](B_3\land\cdots[B_{n-1}](B_n\land[B_n]A)\cdots)) }

(n−1)×m[⋅](n-1)\times\mathrm{m}_{[\cdot]}

B1∧[B1](B2∧[B2](B3∧⋯[Bn−1](Bn∧[Bn]A)⋯ ))⟨B1⋅B2⋯Bn⟩A\frac{ B_1\land[B_1](B_2\land[B_2](B_3\land\cdots[B_{n-1}](B_n\land[B_n]A)\cdots)) }{ \langle B_1\cdot B_2\cdots B_n\rangle A }

(n−1)×r(n-1)\times r

– for ([⋅]0)( [\cdot]_0), we have

G∣X//αΓ,A‾//α⋅ABG∣X//αΓ,[A]B⇝Gτ∨□(Xτ∨(m[⋅]∗[α](Γτ∨A‾)∨[α⋅A]B[α](Γτ∨(A‾∨cA‾[A]B))))\frac{ G\mid X\mathbin{//_{\alpha}}\Gamma,\overline{A}\mathbin{//_{\alpha\cdot A}}B }{ G\mid X\mathbin{//_{\alpha}}\Gamma,[A]B } \quad \leadsto \quad G^\tau\lor\Box\left( X^\tau\lor \left( \mathrm{m}^{*}_{[\cdot]} \frac{[\alpha](\Gamma^\tau\lor\overline{A})\lor[\alpha\cdot A]B} {[\alpha]\left(\Gamma^\tau\lor \left( \overline{A}\lor \mathrm{c}\frac{\overline{A}}{[A]B} \right) \right)} \right) \right)

– for ([⋅]1) G∣X//αΓ,Aˉ //α⋅AΔ,BG∣X//αΓ,[A]B //α⋅AΔ([\cdot]_{1})\ \dfrac{\mathcal{G}\mid X //_{\alpha}\Gamma,\bar{A}\ //_{\alpha\cdot A}\Delta,B}{\mathcal{G}\mid X //_{\alpha}\Gamma,[A]B\ //_{\alpha\cdot A}\Delta} we have

Gτ∨□(Xτ∨[α](Γτ∨Aˉ)∨k[⋅]∗[α⋅A](Δτ∨B)[α⋅A]Δτ∨⟨α⋅A⟩B[α](Γτ∨Aˉ)∨k⟨⋅⟩∗⟨α⋅A⟩B[α⋅A]B∨m[⋅]∗[α](Γτ∨(Aˉ[A]B∨[A]B))[A]B∨[α⋅A]Δτ)\mathcal{G}^{\tau}\vee\Box\left(X^{\tau}\vee \frac{ [\alpha](\Gamma^{\tau}\vee\bar{A})\vee k^{*}_{[\cdot]}\dfrac{[\alpha\cdot A](\Delta^{\tau}\vee B)} {[\alpha\cdot A]\Delta^{\tau}\vee\langle\alpha\cdot A\rangle B} }{ [\alpha](\Gamma^{\tau}\vee\bar{A})\vee k^{*}_{\langle\cdot\rangle}\dfrac{\langle\alpha\cdot A\rangle B} {[\alpha\cdot A]B}\vee m^{*}_{[\cdot]}\dfrac{[\alpha]\left(\Gamma^{\tau}\vee \left(\dfrac{\bar{A}}{[A]B}\vee[A]B\right)\right)} {[A]B} }\vee[\alpha\cdot A]\Delta^{\tau} \right)

– for (⟨⋅⟩0) G∣X//αΓ,AG∣X//αΓ//α⋅ABG∣X//αΓ,⟨A⟩B(\langle\cdot\rangle_{0})\ \dfrac{\mathcal{G}\mid X //_{\alpha}\Gamma,A\qquad\mathcal{G}\mid X //_{\alpha}\Gamma//_{\alpha\cdot A}B}{\mathcal{G}\mid X //_{\alpha}\Gamma,\langle A\rangle B} we have

(Gτ∨□(Xτ∨[α](Γτ∨A)))∧(Gτ∨□(Xτ∨m[⋅]∗[α]Γτ∨[α⋅A]B[α](Γτ∨[A]B)))\left(\mathcal{G}^{\tau}\vee\Box\left(X^{\tau}\vee[\alpha](\Gamma^{\tau}\vee A)\right)\right)\wedge \left(\mathcal{G}^{\tau}\vee\Box\left(X^{\tau}\vee m^{*}_{[\cdot]}\dfrac{[\alpha]\Gamma^{\tau}\vee[\alpha\cdot A]B} {[\alpha](\Gamma^{\tau}\vee[A]B)} \right)\right)
Gτ∨□(Xτ∨[α](Γτ∨rA∧[A]B⟨A⟩B))\mathcal{G}^{\tau}\vee\Box\left(X^{\tau}\vee[\alpha]\left(\Gamma^{\tau}\vee r\dfrac{A\wedge[A]B}{\langle A\rangle B}\right)\right)

where δ′\delta' exists by Lemma 6.4.

– For (⟨⋅⟩1) G∣X//αΓ,A //α⋅AΔG∣X//αΓ//α⋅AΔ,BG∣X//αΓ,⟨A⟩B //α⋅AΔ(\langle\cdot\rangle_{1})\ \dfrac{\mathcal{G}\mid X //_{\alpha}\Gamma,A\ //_{\alpha\cdot A}\Delta\qquad\mathcal{G}\mid X //_{\alpha}\Gamma//_{\alpha\cdot A}\Delta,B}{\mathcal{G}\mid X //_{\alpha}\Gamma,\langle A\rangle B\ //_{\alpha\cdot A}\Delta} we have

(Gτ∨□(Xτ∨[α](Γτ∨A)∨[α⋅A]Δτ))∧(Gτ∨□(Xτ∨[α]Γτ∨k[⋅]∗[α⋅A](Δτ∨B)[α⋅A]Δτ∨⟨α⋅A⟩B[α]Γτ∨k⟨⋅⟩∗⟨α⋅A⟩B[α⋅A]B∨m[⋅]∗[α](Γτ∨[A]B)[α](Γτ∨[A]B)))\left(\mathcal{G}^{\tau}\vee\Box\left(X^{\tau}\vee[\alpha](\Gamma^{\tau}\vee A)\vee[\alpha\cdot A]\Delta^{\tau}\right)\right)\wedge \left( \mathcal{G}^{\tau}\vee\Box\left( X^{\tau}\vee \frac{ [\alpha]\Gamma^{\tau}\vee k_{[\cdot]}^{*}\dfrac{[\alpha\cdot A](\Delta^{\tau}\vee B)} {[\alpha\cdot A]\Delta^{\tau}\vee\langle\alpha\cdot A\rangle B} }{ [\alpha]\Gamma^{\tau}\vee k_{\langle\cdot\rangle}^{*}\dfrac{\langle\alpha\cdot A\rangle B} {[\alpha\cdot A]B}\vee m_{[\cdot]}^{*}\dfrac{[\alpha](\Gamma^{\tau}\vee[A]B)} {[\alpha](\Gamma^{\tau}\vee[A]B)} } \right) \right)
Gτ∨□(Xτ∨[α](Γτ∨rA∧[A]B⟨A⟩B)∨[α⋅A]Δτ)\mathcal{G}^{\tau}\vee\Box\left(X^{\tau}\vee[\alpha]\left(\Gamma^{\tau}\vee r\dfrac{A\wedge[A]B}{\langle A\rangle B}\right)\vee[\alpha\cdot A]\Delta^{\tau}\right)

where δ′\delta' exists by Lemma 6.4.

– For (Atom) G∣X / ⁣/ ⁣α Γ, q / ⁣/ ⁣α⋅A Δ,qG∣X / ⁣/ ⁣α Γ / ⁣/ ⁣α⋅A Δ,q\frac{\mathcal{G}\mid X\ /\!/\!_{\alpha}\ \Gamma,\ q\ /\!/\!_{\alpha\cdot A}\ \Delta,q}{\mathcal{G}\mid X\ /\!/\!_{\alpha}\ \Gamma\ /\!/\!_{\alpha\cdot A}\ \Delta,q} we construct

\mathcal{G}^{\tau}\vee\Box\ \middle|\ X^{\tau}\vee \left( \frac{ [\alpha]\left(\Gamma^{\tau}\vee e_{[\cdot]}\left[\frac{q}{[A]q}\right]\right)\vee[\alpha\cdot A](\Delta^{\tau}\vee q) }{ [\alpha]\Gamma^{\tau}\vee\langle\alpha\rangle[A]q } \ \vee\ \frac{ [\alpha\cdot A](\Delta^{\tau}\vee q)\vee k^{*}_{\langle\cdot\rangle}\frac{\langle\alpha\rangle[A]q}{[\alpha\cdot A]q} }{ [\alpha]\Gamma^{\tau}\vee m^{*}_{[\cdot]}\frac{q\vee q}{q} } \right)

– For (New), we have

\frac{\mathcal{G}\mid X\ /\!/\!_{\alpha}\ /\!/\!_{\alpha\cdot A}\Delta}{\mathcal{G}\mid X\ /\!/\!_{\alpha\cdot A}\Delta} \leadsto \mathcal{G}^{\tau}\vee\Box\ \middle|\ X^{\tau}\vee \left( \frac{m^{*}_{[\cdot]}[\alpha]\bot\vee[\alpha\cdot A]\Delta^{\tau}}{[\alpha]\left(\bot\vee[A]\Delta^{\tau}\right)} \right) \equiv \frac{\bot\vee[A]\Delta^{\tau}}{[A]\Delta^{\tau}}

– For (Recall) G∣X / ⁣/ ⁣α Γ, Aˉ / ⁣/ ⁣α⋅A ΔG∣X / ⁣/ ⁣α Γ / ⁣/ ⁣α⋅A Δ\frac{\mathcal{G}\mid X\ /\!/\!_{\alpha}\ \Gamma,\ \bar{A}\ /\!/\!_{\alpha\cdot A}\ \Delta}{\mathcal{G}\mid X\ /\!/\!_{\alpha}\ \Gamma\ /\!/\!_{\alpha\cdot A}\ \Delta} we have

\mathcal{G}^{\tau}\vee\Box\ \middle|\ X^{\tau}\vee \left( \frac{ k^{*}_{[\cdot]}\frac{[\alpha](\Gamma^{\tau}\vee\bar{A})}{[\alpha]\Gamma^{\tau}\vee\langle\alpha\rangle\bar{A}}\vee[\alpha\cdot A]\Delta^{\tau} }{ [\alpha]\Gamma^{\tau}\vee m^{*}_{[\cdot]}\frac{k^{*}_{\langle\cdot\rangle}\frac{\langle\alpha\rangle\bar{A}}{[\alpha]\bar{A}}\vee[\alpha\cdot A]\Delta^{\tau}}{ [\alpha]\left(\bar{A}\vee\left(\frac{\bar{A}}{[A]\Delta^{\tau}}\vee[A]\Delta^{\tau}\right)\right) } \right)}

References

  1. [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. [2]Ágotnes, T., Balbiani, P., van Ditmarsch, H., Seban, P.: Group announcement logic. Journal of Applied Logic 8(1), 62–81 (2010)
  3. [3]Artemov, S., Protopopescu, T.: Intuitionistic epistemic logic. The Review of Symbolic Logic 9(2), 266–298 (2016)
  4. [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. [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. [6]Balbiani, P., van Ditmarsch, H., Gencer, C., Lerouillois, C.: A minimal intuitionistic public announcement logic (2026)arxiv.org/abs/2611.14408
  7. [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. [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. [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. [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. [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. [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. [13]van Benthem, J., van Eijck, J., Kooi, B.: Logics of communication and change. Information and computation 204(11), 1620–1662 (2006)
  14. [14]de Boer, M.: Ke tableaux for public announcement logic. In: Formal Approaches to Multi-Agent Systems Workshop (FAMAS’007) (2007)
  15. [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. [16]Brünnler, K.: Cut elimination inside a deep inference system for classical predicate logic. Studia Logica 82(1), 51–71 (2006)
  17. [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. [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. [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. [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. [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. [22]van Ditmarsch, H., Hoek, W., Kooi van Der, B.: Dynamic epistemic logic, vol. 337. Springer Science & Business Media (2007)
  23. [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. [24]Gerbrandy, J., Groenveld, W.: Reasoning about information change. Journal of logic, language and information 6, 147–169 (1997)DOI
  25. [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. [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. [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. [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. [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. [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. [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. [32]Hintikka, J.: Knowledge and belief: An introduction to the logic of the two notions. Studia Logica 16 (1962)
  33. [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. [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. [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. [36]Lerouvillois, C., Poggiolesi, F.: Dynamic proof theory for dynamic epistemic logic (2026), https://arxiv.org/abs/2609.37440
  37. [37]Lin, Z., Gao, Z., Zhao, Z.: Gentzen sequent calculi for intuitionistic public announcement logic (11 2025)
  38. [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. [39]Liu, S., Sano, K.: Sequent calculi for public announcement logic and action model logic. Synthese 208(3), 106 (2026)DOI
  40. [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. [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. [42]Maehara, S.: Craig no interpolation theorem. Suugaku 12, 235–237 (1960)
  43. [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. [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. [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. [46]Plaza, J.: Logics of public announcements. In: Proceedings 4th international symposium on methodologies for intelligent systems. pp. 201–216 (1989)
  47. [47]Prior, A.N.: Time and modality. Oxford University Press (2003)
  48. [48]Servi, F.: Axiomatizations for some intuitionistic modal logics. Rendiconti del Seminario Matematico Università e Politecnico di Torino 42 (1984)
  49. [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. [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. [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. [52]Straßburger, L.: Interpolation via generalized splitting. arXiv preprint arXiv:2607.23798 (2026)
  53. [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. [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. [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. [56]Wang, Y., Cao, Q.: On axiomatizations of public announcement logic. Synthese 190(Suppl 1), 103–134 (2013)DOI
  57. [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. [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. [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

Paper details

vlnc:W_nd287r7w
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents