💻 computer science

Hennessy-Milner Logic in CSLib, the Lean Computer Science Library

This paper presents a general, reusable formalization of Hennessy-Milner Logic within the Lean Computer Science Library (CSLib), featuring a complete metatheory that includes the Hennessy-Milner theorem and leverages Lean's automation to support arbitrary image-finite labelled transition systems.

Original authors: Fabrizio Montesi, Marco Peressotti, Alexandre Rademaker

Published 2026-02-18

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Fabrizio Montesi, Marco Peressotti, Alexandre Rademaker

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 have a massive, complex machine—like a video game character, a traffic light system, or a robot vacuum. You want to know: "How does this thing behave?" and "Is it behaving exactly the same way as that other machine?"

In computer science, we use a framework called a Labelled Transition System (LTS) to map out every possible move a machine can make. Think of an LTS as a giant, branching "Choose Your Own Adventure" book where every page is a state, and every arrow is a move labeled with an action (like "press start," "move left," or "send message").

The paper you're asking about is about building a universal rulebook (called Hennessy–Milner Logic, or HML) to describe these machines, and proving that this rulebook is perfectly accurate.

Here is the breakdown of their work using simple analogies:

1. The Problem: "Are these two machines twins?"

Imagine you have two robots, Robot A and Robot B.

Robot A can press a button and move to a room with a cat.
Robot B can press a button and move to a room with a dog.

To a human, they are different. But what if they are incredibly complex? How do we prove they are exactly the same (or different) without testing every single possible future scenario?

Computer scientists use Bisimulation. This is like a "mirror test." If Robot A makes a move, Robot B must be able to make a matching move to a state that looks just as good. If they can keep mirroring each other forever, they are "bisimilar" (twins).

2. The Solution: The "Logic Language" (HML)

The authors created a special language (HML) to describe these machines. Instead of saying "Robot A goes to the cat room," they use logical sentences like:

"Diamond" ( $\langle \mu \rangle$ ): "It is possible to press button $\mu$ and end up in a state where $\phi$ is true." (Like saying: "There is a path to the treasure.")
"Box" ( $[\mu]$ ): "No matter how you press button $\mu$ , you must end up in a state where $\phi$ is true." (Like saying: "Every path leads to safety.")

They built this language inside Lean, a powerful tool that acts like a super-strict math teacher. Lean checks every single step of their logic to ensure there are no mistakes.

3. The Big Achievement: The "Mirror Theorem"

The most famous part of their work is proving the Hennessy–Milner Theorem.

Think of it this way:

Bisimulation is checking if two machines move in perfect sync physically.
Theory Equivalence is checking if two machines answer "Yes" to the exact same list of questions in our Logic Language.

The authors proved a magical fact: For machines that don't have infinite branching possibilities (called "image-finite"), these two checks are identical.

If two machines answer the same questions in our logic language, they are physically identical twins. If they are physically identical twins, they answer the same questions. It's a perfect 1-to-1 match.

4. Why This Paper Matters (The "CSLib" Part)

Before this, people had written code to check these things, but it was often messy, specific to one type of robot, or hard to reuse.

The authors built this logic as a library (a toolbox) called CSLib.

Analogy: Imagine previous researchers built a custom wrench for a specific bolt. The authors built a universal, high-quality socket set that fits any bolt.
Reusability: Because they built it into the "Lean Computer Science Library," anyone else working on automata, communication protocols, or software verification can just grab this toolbox and use it immediately. They don't have to reinvent the wheel.
Automation: They used a special tactic called grind (think of it as a "magic eraser" or "auto-pilot") that automatically solves the boring, repetitive math proofs, letting the researchers focus on the big ideas.

Summary

In short, these researchers built a universal, error-proof dictionary for describing how computer systems behave. They proved that this dictionary is so accurate that if two systems speak the same "language" in this dictionary, they are guaranteed to be behaving identically in the real world.

They packaged this dictionary into a shared toolbox so that other computer scientists can use it to build safer, more reliable software without having to do the heavy lifting themselves.

Based on the paper "Hennessy–Milner Logic in CSLib, the Lean Computer Science Library," here is a detailed technical summary covering the problem, methodology, contributions, results, and significance.

1. Problem Statement

Labelled Transition Systems (LTSs) are the standard framework for defining the operational behavior of computational systems (e.g., process calculi, protocols, automata). Hennessy–Milner Logic (HML) is a foundational modal logic used to reason about these systems. Its most significant property is the Hennessy–Milner theorem, which establishes that for image-finite LTSs, two states are strongly bisimilar if and only if they satisfy exactly the same set of HML propositions (theory equivalence).

Despite HML's foundational status, the paper identifies a gap in existing formalizations:

Lack of Library-Grade Generality: Existing mechanized treatments in theorem provers often focus on specific variations of HML or specific types of LTSs rather than a general, reusable library component.
Fragmentation: There is a need for a unified, high-quality formalization within the Lean Computer Science Library (CSLib) that integrates seamlessly with other formalized computer science theories (like automata and process calculi) defined in the same ecosystem.

2. Methodology

The authors developed a formalization of HML using Lean 4, specifically designed to integrate with CSLib and Mathlib (the Lean mathematical library). Their methodology emphasizes:

Parametric Design: Definitions are universe-polymorphic and parametric over arbitrary types for states and transition labels. This ensures the logic applies to any system modeled as an LTS within the library.
Integration with Existing Infrastructure: The formalization leverages CSLib's existing definitions for LTSs and bisimilarity, avoiding redundancy.
Automation: The proofs heavily utilize Lean's automation, specifically the grind tactic, to handle repetitive proof obligations involving set operations and inductive structures.
Dual Semantics Approach: The authors formalized both the inductive satisfaction relation (operational semantics) and the denotational semantics (mapping propositions to sets of states) to prove their equivalence.

3. Key Contributions

The paper presents three main contributions:

A. Formalization of HML Core Components

The authors defined the following components as reusable Lean structures:

Syntax: An inductive type for HML propositions including true, false, conjunction (∧), disjunction (∨), diamond modality (⟨µ⟩), and box modality ([µ]). They adopted a variant without explicit negation in the syntax (using false instead) to simplify the satisfaction definition, recovering negation via a derived function.
Satisfaction Relation (Satisfies): An inductive definition determining when a state satisfies a proposition based on the transition relation.
Denotational Semantics: A function mapping each proposition to the set of states that satisfy it.
Theory Equivalence: A definition stating that two states are equivalent if they satisfy the exact same set of propositions.

B. Complete Metatheory

The authors proved the fundamental theoretical properties of HML:

Semantic Equivalence: Proved that the inductive satisfaction relation coincides with the denotational semantics (i.e., $s \models \phi \iff s \in \llbracket \phi \rrbracket$ ).
Bisimulation Invariance: Proved that if two states are bisimilar, they satisfy the same propositions.
The Hennessy–Milner Theorem: Proved the converse: for image-finite LTSs, if two states satisfy the same propositions (Theory Equivalence), they are bisimilar.
- Technical Note: The proof for the converse relies on the image-finiteness condition to construct a distinguishing proposition for any non-bisimilar pair by collecting all possible derivatives and forming a finite disjunction.

C. Integration and Reusability

The code is part of the official CSLib repository (Cslib.Logic.HML).
It provides APIs that allow downstream projects (such as the formalization of the Calculus of Communicating Systems (CCS) and Automata Theory within CSLib) to immediately inherit these results.
The authors demonstrated this by proving that theory equivalence coincides with bisimilarity for CCS processes, provided they satisfy the image-finiteness condition (e.g., via guarded recursion).

4. Results

Correctness: The formalization successfully proves the correctness of the denotational semantics and the full Hennessy–Milner theorem within Lean 4.
Automation Success: The use of the grind tactic allowed for the automatic resolution of most proof cases, particularly in the semantic equivalence and bisimulation invariance proofs. The only manual intervention required was a minor hint for the bisimulation case in the diamond modality.
Applicability: The library successfully applies to existing CSLib components. The example provided shows that the general theorem theoryEq_eq_bisimilarity can be instantiated directly for CCS models without rewriting the logic.

5. Significance

Foundational Infrastructure: This work establishes the first modal logic formalization in CSLib, serving as a reference implementation for future extensions (e.g., weak equivalences, fixpoint operators, or logics for $\pi$ -calculus).
Generality: Unlike previous works that target specific calculi, this formalization is generic. It decouples the logic from specific system implementations, allowing it to be applied to any system adhering to the CSLib LTS API.
Bridging Theory and Practice: By integrating with a growing community library (CSLib), it facilitates verified software development and research in concurrency theory, making advanced metatheoretical results (like the Hennessy–Milner theorem) readily available to developers and researchers using Lean.
Future Directions: The authors note that while the current work handles strong bisimilarity and standard HML, future work will address extensions for weak equivalences and logics capable of handling bound variables (essential for $\pi$ -calculus), which require more complex nominal reasoning.

In summary, the paper delivers a robust, general, and automated formalization of Hennessy–Milner Logic that bridges the gap between abstract concurrency theory and practical, verified software development within the Lean ecosystem.