Craig interpolation in test-free propositional dynamic logic

Propositional dynamic logic describes what holds after executing a program. Craig interpolation asks whether a valid implication can be split into two implications through a formula using only symbols shared by its two sides. Does that still work if formulas cannot test a condition inside a program?

Why it matters and what counts as progress

Why it matters: Interpolation lets two descriptions communicate through their common vocabulary. This question tests whether tests inside programs are needed for that property.

What counts as progress: A proof would construct an interpolant in the test-free language for every valid implication. A counterexample must give a valid implication and rule out every test-free interpolant over its common vocabulary.

How the problem developed

  1. 2025 · Full-language proof [3]

    Manfred Borzechowski and colleagues Posted a tableau proof of Craig interpolation for full propositional dynamic logic.

  2. 12 Nov 2026 · Counterexample [1][2]

    Malvin Gattinger with Claude Fable Published a simplified version of the model’s counterexample for the test-free language.

AI contribution

Sources

  1. Propositional Dynamic Logic without tests does not have Craig Interpolation
  2. Gattinger’s formal counterexample
  3. Borzechowski and colleagues’ proof for full dynamic logic
Publication history