Propositional Dynamic Logic without tests does not have Craig Interpolation

Malvin Gattinger

Gattinger gives a valid implication in propositional dynamic logic using one atomic program and its Kleene star, with no tests and no test-free Craig interpolant.

What was already known

Borzechowski and colleagues proved interpolation for full propositional dynamic logic. Whether its test-free fragment retained interpolation was open.

AI involvement AI-centered

Claude Fable found and formalized the first counterexample after Gattinger posed the reverse question. Gattinger simplified the example and wrote the paper.

Importance Notable

A counterexample shows that removing the test operator can destroy interpolation even when the language retains program iteration.

Technical verification Formal (Lean 4)

The paper links the Lean development, whose public proof documentation includes the theorem that test-free propositional dynamic logic lacks interpolation.

Formal checking

The paper links the Lean development, whose public proof documentation includes the theorem that test-free propositional dynamic logic lacks interpolation.

Checker
Lean 4 in Gattinger’s formalization
Scope
Machine checked the validity and absence of a test-free interpolant in the documented formal model.
Basis
Reported by the linked checker

Human understanding Explained

Gattinger explains how the two sides of the implication can be distinguished in the full language while suitable pairs of model states agree on formulas in the shared test-free vocabulary.

Correction and publication history