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
- 2025 · Full-language proof [3]
Manfred Borzechowski and colleagues Posted a tableau proof of Craig interpolation for full propositional dynamic logic.
Malvin Gattinger with Claude Fable Published a simplified version of the model’s counterexample for the test-free language.
AI contribution
Propositional Dynamic Logic without tests does not have Craig Interpolation
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.
Sources
Publication history
Propositional Dynamic Logic without tests does not have Craig Interpolation
Daily emails by default, only when there’s an update.