Propositional Dynamic Logic has Craig Interpolation: a tableau-based proof
Manfred Borzechowski, Malvin Gattinger ORCID:0000-0002-2498-5073, Helle Hvid Hansen ORCID:0000-0001-7061-1219, Revantha Ramanayake ORCID:0000-0002-7940-9065, Francisco Trucco Dalmas ORCID:0000-0003-2493-023X, Yde Venema · 2025
Read Propositional Dynamic Logic has Craig Interpolation: a tableau-based proof by Manfred Borzechowski, Malvin Gattinger ORCID:0000-0002-2498-5073, Helle Hvid Hansen ORCID:0000-0001-7061-1219, Revantha Ramanayake ORCID:0000-0002-7940-9065, Francisco Trucco Dalmas ORCID:0000-0003-2493-023X, Yde Venema (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-13276.txt.
Introduction
Manfred Borzechowski and co-authors settle a long-open question: a logic of programs does enjoy the Craig interpolation property. Their 2025 paper proves the claim for Propositional Dynamic Logic. Three past proof tries were later criticized or withdrawn, so a sound proof was still missing.
The proof builds a cyclic tableau system with a loading trick that spots good repeats. Soundness and completeness come through a game reading of the system. Interpolation adapts a classic method to tableaux with repeats, solving fixed-point equations cluster by cluster. The method is constructive: it tells how to compute the in-between formula. Code in Haskell ships with the work, and a formal check in Lean is under way.
Catalog record
| CREATOR | Manfred Borzechowski, Malvin Gattinger ORCID:0000-0002-2498-5073, Helle Hvid Hansen ORCID:0000-0001-7061-1219, Revantha Ramanayake ORCID:0000-0002-7940-9065, Francisco Trucco Dalmas ORCID:0000-0003-2493-023X, Yde Venema |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 341 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-13276