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

CREATORManfred 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
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE341 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-13276

Browse the full library · About the Tower of Babel