💻 computer science

Dynamic Hypersequents for Public Announcement Logic

This paper introduces dynamic hypersequents, a novel proof-theoretic framework extending hypersequent calculi to Public Announcement Logic, which successfully captures the dynamism of epistemic updates and establishes key properties such as structural rule admissibility, rule invertibility, and syntactic cut-elimination.

Original authors: Clara Lerouvillois, Francesca Poggiolesi

Published 2026-05-18

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Clara Lerouvillois, Francesca Poggiolesi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a game of "Guess Who?" with a friend. You both have a board full of characters. At the start, everyone is a possibility. But then, your friend says, "The culprit is wearing a hat." Suddenly, you can cross off everyone without a hat. The game has changed; the "world" of possibilities has shrunk.

This is the core idea of Public Announcement Logic (PAL). It's a branch of logic that studies how our knowledge changes when new information is announced to everyone.

However, there's a problem. While mathematicians are very good at describing what happens to the game board (the semantics), they have struggled to build a perfect "rulebook" (a proof system) that captures this changing nature using only the rules of the game itself, without peeking at the board. Existing rulebooks were either too clunky or missed the dynamic "flow" of the game.

This paper, by Clara Lerouvillois and Francesca Poggiolesi, introduces a new, elegant way to write this rulebook. Here is how they did it, using some creative analogies:

1. The Old Way vs. The New Way

The Old Way (Standard Logic):
Think of a standard logic proof as a single, static snapshot. It's like a photograph of the game board at one specific moment. If the game changes, you have to take a completely new photo and start a new proof. It doesn't show the transition from one state to another.

The New Way (Dynamic Hypersequents):
The authors propose a new structure called Dynamic Hypersequents. Imagine this not as a single photo, but as a multi-layered comic strip or a spreadsheet.

The Rows: Each row represents a different character (or "world") in the game.
The Columns: Each column represents a different moment in time, specifically after a new announcement has been made.

So, a single "Dynamic Hypersequent" isn't just one state; it's a single object that holds the entire history of the game: the starting board, the board after the first announcement, the board after the second, and so on. It captures the "movie" of the logic, not just the "frames."

2. How the Rules Work

In this new system, the rules of the game are designed to handle these "movies."

The "Announcement" Rules: When a new fact is announced (e.g., "The culprit is wearing a hat"), the rules don't just delete things. They create a new column in the spreadsheet. They check: "If this character was in the previous column, are they still valid in the new column?" If the character doesn't fit the new fact, they disappear from that specific column, but they might still exist in the previous columns (the past).
The "Knowledge" Rules: The system also handles what characters know. If a character knows something, they must know it in all the "possible worlds" (rows) they can see. The new rules ensure that if a character knows something in the current updated world, that knowledge is consistent with how the world got there.

3. Why This Matters (The "Magic" Results)

The authors didn't just draw pretty pictures; they proved that their new rulebook works perfectly. They showed that their system has three "superpowers" that previous systems lacked:

No "Cheating" (Cut-Elimination): In logic, a "cut" is like using a shortcut or a lemma you haven't proven yet. The authors proved you don't need shortcuts. You can prove everything using only the basic steps right in front of you. This makes the logic "clean" and reliable.
Everything is Reversible (Invertibility): Usually, in logic, if you go from Step A to Step B, you can't always go back. In this new system, every step is reversible. If you have the result, you can perfectly reconstruct the steps that led to it. This is like having a "Undo" button that works perfectly for every move in the game.
No Redundancy (Contraction): The system handles duplicates naturally. If you have the same piece of information twice, the rules know how to merge them without breaking the logic.

The Big Picture

The paper claims that by using these Dynamic Hypersequents (our multi-layered comic strips), they have built a proof system for Public Announcement Logic that is:

Complete: It can prove every true statement in this logic.
Sound: It never proves a false statement.
Structurally Beautiful: It handles the "dynamic" nature of changing information using pure structural rules, without needing to add messy external labels or semantic tricks.

In short, they found a way to write a rulebook for a changing world that stays true to the changing nature of the world itself, all while keeping the math clean, reversible, and shortcut-free.

Technical Summary: Dynamic Hypersequents for Public Announcement Logic

Problem Statement
Dynamic Epistemic Logic (DEL), and specifically Public Announcement Logic (PAL), models the evolution of knowledge through information updates. While the semantics of PAL are well-understood as transformations of Kripke models (where an announcement restricts the set of possible worlds), existing proof-theoretic frameworks struggle to capture this dynamism at the syntactic level. Previous attempts, including tableau methods and various sequent calculi (labelled and non-labelled), often fail to simultaneously achieve a genuine subformula property, the admissibility of all structural rules (including contraction), and syntactic cut-elimination. Many existing systems rely on reduction axioms that translate dynamic formulas into static ones, thereby obscuring the dynamic nature of the logic within the proof system itself.

Methodology
The authors propose a new proof-theoretic framework based on dynamic hypersequents. This approach extends the hypersequent calculus for S5 (introduced in [15, 16]) by incorporating a mechanism to model transitions between epistemic models induced by public announcements.

Dynamic Sequents: A dynamic sequent is defined as a sequence of standard sequents labeled by distinct finite sequences of announcements (e.g., $\alpha_1 \Gamma_1 | \dots | \alpha_n \Gamma_n$ ). Intuitively, a dynamic sequent represents a specific world $w$ in an initial model $M$ and its "copies" in successively updated models $M_{\alpha}$ .
Dynamic Hypersequents (DHS): A dynamic hypersequent is a collection of dynamic sequents. This structure syntactically represents an entire epistemic model and its successive updates simultaneously. The authors interpret a DHS as a disjunction of boxed formulas, where each component corresponds to a world in the model or its updates.
The Calculus ($DHSPAL$): The authors define a calculus $DHSPAL$ comprising:
- Propositional and Modal Rules: Adapted from standard hypersequent calculi for S5.
- Announcement Rules: Rules $(L[\cdot])$ and $(R[\cdot])$ that decompose public announcement formulas $[A]B$ . These rules explicitly manage the transition from a current state to an updated state by introducing new dynamic sequents labeled with the extended announcement sequence $\alpha \cdot A$ .
- Dynamic Structural Rules: Specific rules such as $(Lat)$ and $(Rat)$ (Atomic Permanence), $(New)$ (ensuring worlds in updated models exist in previous ones), and $(Recall)$ (ensuring the announced formula holds in the previous model).
- Dynamic Modal Rule: A specialized rule $(L\Box_3)$ that handles the interaction between knowledge ( $\Box$ ) and sequences of announcements, distinguishing between worlds that survive an update and those that do not.

Key Contributions and Results
The paper establishes that $DHSPAL$ is a robust proof system for PAL, achieving several properties that previous systems lacked simultaneously:

Admissibility of Structural Rules: The authors prove the hp-admissibility (height-preserving admissibility) of weakening, contraction, and a merge rule. Crucially, this includes contraction, which is often difficult to achieve in dynamic logics without losing analyticity.
Invertibility of Logical Rules: All logical rules in the calculus are shown to be hp-invertible. This property is essential for proof search and establishing cut-elimination.
Syntactic Cut-Elimination: The paper provides a proof of the admissibility of the Cut rule. The proof relies on a double induction: one on the DHS-complexity of the cut-formula (a complexity measure relative to the announcement sequence) and another on the sum of the heights of the derivations of the premises.
Soundness and Completeness: The calculus is proven sound and complete with respect to the standard Kripke semantics of PAL. The completeness proof involves deriving all Hilbert-style axioms of PAL, including the reduction axioms, within the dynamic hypersequent framework.
Subformula Property: As a consequence of cut-elimination, the calculus enjoys the subformula property, ensuring that any formula in a derivation is a subformula of the end-sequent or an announcement occurring within it.

Significance and Claims
The authors claim that this work represents a significant step toward addressing the gap between the semantic dynamism of PAL and its syntactic proof theory. By using dynamic hypersequents, the system captures the dynamic character of the logic through purely structural means, avoiding the need for explicit semantic elements (like labels for worlds) or reduction to static logic.

The paper asserts that, to their knowledge, $DHSPAL$ is the first calculus for PAL that simultaneously satisfies:

Admissibility of all structural rules (including contraction).
Invertibility of all logical rules.
Syntactic cut-elimination.
A genuine subformula property.

The authors conclude that the framework of dynamic hypersequents is sufficiently expressive and robust to serve as a foundation for developing sequent calculi for broader classes of dynamic epistemic logics involving different types of information updates. They suggest future work could explore decidability, interpolation, and complexity analysis within this framework.

1. The Old Way vs. The New Way

2. How the Rules Work

3. Why This Matters (The "Magic" Results)

The Big Picture

More like this