Search papers, labs, and topics across Lattice.
This paper formalizes Hennessy-Milner Logic (HML) within the Lean Computer Science Library (CSLib), providing a reusable and general framework for reasoning about labelled transition systems (LTSs). The formalization includes the syntax, satisfaction relation, and denotational semantics of HML, along with a complete metatheory culminating in the Hennessy-Milner theorem. By leveraging Lean's automation and integrating with CSLib's existing formalizations, the work enables easier application of HML to systems formalized within CSLib.
Formalizing Hennessy-Milner Logic in Lean's CSLib provides a reusable and verified foundation for reasoning about labelled transition systems.
We present a library-level formalisation of Hennessy-Milner Logic (HML) - a foundational logic for labelled transition systems (LTSs) - for the Lean Computer Science Library (CSLib). Our development includes the syntax, satisfaction relation, and denotational semantics of HML, as well as a complete metatheory including the Hennessy-Milner theorem - bisimilarity coincides with theory equivalence for image-finite LTSs. Our development emphasises generality and reusability: it is parametric over arbitrary LTSs, definitions integrate with CSLib's infrastructure (such as the formalisation of bisimilarity), and proofs leverage Lean's automation (notably the grind tactic). All code is publicly available in CSLib and can be readily applied to systems that use its LTS API.
