💻 computer science

On Propositional Dynamic Logic and Concurrency

This paper introduces Operational Propositional Dynamic Logic (OPDL), a generalized framework that overcomes the limitations of traditional dynamic logic in modeling concurrency by decoupling programs from their traces and utilizing a parameterized operational semantics, supported by a novel cut-elimination proof for a non-wellfounded sequent calculus.

Original authors: Matteo Acclavio, Fabrizio Montesi, Marco Peressotti

Published 2026-04-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Matteo Acclavio, Fabrizio Montesi, Marco Peressotti

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to write a rulebook for a massive, chaotic dance party.

In the world of computer science, this "dance" is a program. The "rules" are logic, a way to prove that the program will behave the way we expect it to.

For decades, logicians have used a system called Propositional Dynamic Logic (PDL) to write these rulebooks. Think of PDL as a translator that turns a computer program into a story about its possible paths.

If the program is a simple, straight-line dance (sequential), PDL is great. It says, "If you do step A, then step B, you will end up in a happy state."
But what if the dance is concurrent? What if two dancers are moving at the same time, and they can swap places, interrupt each other, or do things in a different order? This is the "interleaving" problem.

The Old Problem: The "Trace" Trap

Traditionally, PDL treated programs like a list of traces (a trace is just a single, recorded history of what happened).

The Analogy: Imagine you are trying to prove that two different dance routines are the same. The old method said, "Okay, let's list every single possible way the dancers could move."
The Problem: In a concurrent system, the dancers can swap steps in millions of different ways. If Dancer A does "Spin" and Dancer B does "Jump," it doesn't matter if A spins first or B jumps first; the result is the same.
The Math Nightmare: Trying to list every possible order of these swaps to prove two programs are equal is like trying to count every grain of sand on a beach to prove two beaches are the same size. It's mathematically impossible (undecidable) for complex systems. The old logic got stuck in a loop, unable to decide if two programs were truly equivalent.

The New Solution: OPDL (The "Director" Approach)

The authors of this paper, Matteo, Fabrizio, and Marco, invented a new framework called Operational Propositional Dynamic Logic (OPDL).

Instead of looking at the list of all possible histories (the traces), OPDL looks at the Director's Script (the operational semantics).

The Analogy: Imagine you are the Director of the dance.
- Old Way (PDL): You try to write down every single possible recording of the dance to prove two versions are the same. You get overwhelmed by the chaos.
- New Way (OPDL): You don't care about the recordings. You look at the rules of the dance floor. You say, "The rule is: Dancer A can spin anytime Dancer B isn't touching them."
- By defining the rules (the operational semantics) separately from the story (the logic), OPDL allows the logic to handle the chaos without getting lost in the details. It separates the "what" (the program) from the "how" (the execution).

How They Proved It Works: The "Infinite Ladder"

To make sure their new logic is solid, they had to prove a very difficult mathematical thing called Cut-Elimination.

The Metaphor: Imagine you are climbing a ladder to prove a theorem. Usually, you can climb up, take a shortcut (a "cut"), and jump to the top. But sometimes, taking shortcuts creates a mess where you can't be sure you actually reached the top.
The Innovation: The authors built a new, infinite ladder. They proved that even if you have an infinitely tall ladder (because concurrent programs can run forever), you can always remove the shortcuts and still reach the top safely. They showed that their logic is "clean"—you don't need magic tricks to prove things; the rules themselves are enough.

Two Real-World Dance Floors

To show off their new system, they tested it on two very different types of "dance floors":

CCS (The Parallel Dance):
- This is like a standard dance floor where two people are dancing side-by-side. They can do their own moves, or they can high-five (synchronize).
- The Win: OPDL can prove that two different ways of organizing this parallel dance result in the same outcome, something the old logic struggled with.
Choreographic Programming (The Out-of-Order Dance):
- This is like a modern, high-tech dance where instructions are sent to different dancers, and they execute them as soon as they are ready, regardless of the order they were written.
- The Win: This is the "out-of-order execution" problem. OPDL handles this beautifully because it focuses on the rules of who can move when, rather than trying to list every possible order of moves.

Why This Matters

Before this paper, if you wanted to verify a complex, concurrent computer system (like a self-driving car's software or a blockchain), you had to use a different, messy logic for every specific type of system. It was like having a different rulebook for every different sport.

OPDL is the "Universal Rulebook."
It provides a single, flexible framework that can adapt to any programming language. Whether the language uses parallel threads, out-of-order execution, or complex recursion, OPDL can translate it into a logical proof.

In short: They took a logic system that was stuck trying to count every grain of sand on a beach, and gave it a map of the beach instead. Now, it can navigate the chaos of concurrent computing with ease.

1. Problem Statement

The paper addresses the fundamental difficulty of applying Propositional Dynamic Logic (PDL) to concurrent systems.

The Core Issue: Traditional PDL represents programs as sets of traces (sequences of actions), modeled as elements of a Kleene algebra. For sequential programs, trace equivalence is decidable. However, in concurrency, traces differ by interleaving (e.g., $a;b$ is equivalent to $b;a$ if $a$ and $b$ are independent).
The Undecidability Barrier: Capturing interleaving requires adding commutation equations ( $\alpha; \beta = \beta; \alpha$ ) to the Kleene algebra. It is a known result that the word problem (deciding equality) for Kleene algebras enriched with such commutations is undecidable. Consequently, standard PDL cannot effectively reason about concurrency, as it cannot decide if two modalities (programs) are equivalent.
Limitations of Existing Work: Previous attempts to extend PDL to concurrency (e.g., Concurrent PDL) often lack expressivity (missing features like nested parallelism, synchronization, or recursion) or require ad-hoc, non-uniform technical developments for each specific concurrency model.

2. Methodology: Operational Propositional Dynamic Logic (OPDL)

The authors propose a new framework called Operational Propositional Dynamic Logic (OPDL) that fundamentally decouples the reasoning about programs from the reasoning about their traces.

Separation of Concerns: Instead of defining programs as regular expressions over traces, OPDL treats programs as syntactic entities governed by an arbitrary operational semantics.
Parameterization: The logic is parameterized by a specific operational semantics (a labeled transition system). Traces are generated dynamically by this semantics rather than being pre-defined as a static set.
The Operational Axiom ( $A_O$ ): The core innovation is a new axiom schema that bridges the program syntax and its operational behavior:
$[\alpha]\phi \iff \bigvee_{\alpha \xrightarrow{\beta} \gamma} [\beta][\gamma]\phi$
This axiom states that a program $\alpha$ satisfies $\phi$ if and only if, for every possible transition $\alpha \xrightarrow{\beta} \gamma$ , the resulting state satisfies $[\beta][\gamma]\phi$ . This allows the logic to "unfold" programs based on their specific operational rules.

3. Key Technical Contributions

A. Cut-Elimination for Non-Wellfounded Sequent Calculus

To establish the theoretical foundation, the authors provide the first cut-elimination proof for a finitely-branching, non-wellfounded sequent calculus for PDL (denoted as $LPD$).

Challenge: Standard cut-elimination relies on confluence, which fails in classical logic extensions due to critical pairs (e.g., Lafont critical pairs).
Solution: The authors adapt techniques from infinitary rewriting and Scott domains. They define a deterministic cut-elimination strategy that handles non-confluence by fixing a specific reduction order. They prove that the limit of this strategy yields a well-defined, cut-free derivation that preserves the "progressing" condition (essential for handling infinite derivations in non-wellfounded systems).
Significance: This result allows the authors to prove soundness and completeness of PDL with respect to its axiomatization without relying directly on semantic arguments, providing a robust proof-theoretic foundation.

B. Embedding Operational Semantics

The authors extend the sequent calculus to LOPD (for OPDL) by adding rules corresponding to the operational axiom $A_O$ .

They prove that cut-elimination holds for this extended system.
They establish Soundness and Completeness: A formula is derivable in OPDL if and only if it is valid in the Kripke models defined by the specific operational semantics.
Trace Equivalence: They prove that logical equivalence in OPDL ( $\vdash [\alpha]\phi \leftrightarrow [\beta]\phi$ ) corresponds exactly to trace equivalence ( $\alpha \sim_{Tr} \beta$ ) defined by the operational semantics.

4. Results and Case Studies

The authors demonstrate the versatility of OPDL by instantiating it for two distinct concurrency models, showing it can handle features previously out of reach for PDL.

Case Study 1: CCS (Calculus of Communicating Systems)

Model: Processes interact via parallel composition with interleaving and synchronization (silent $\tau$ actions).
Achievement: OPDL successfully captures trace equivalence for CCS, including recursion and parallel composition.
Examples: The paper derives standard laws (e.g., commutativity of parallel composition, distribution of prefixes over choice) and proves equivalences between processes that are trace-equivalent but not bisimilar (e.g., $(\alpha.\beta.\pi_1) + (\alpha.\gamma)$ vs. $\alpha.(\beta.\pi_2 + \gamma)$ ).
Advantage: Unlike previous PDL approaches, this handles nested parallelism and recursion natively without encoding them as complex regular expressions.

Case Study 2: Choreographic Programming

Model: A paradigm where concurrency arises from out-of-order execution of independent instructions across distributed processes, rather than explicit parallel operators.
Achievement: OPDL captures the semantics where instructions involving disjoint sets of processes can be reordered (e.g., $I_1; I_2 \sim_{Tr} I_2; I_1$ if they don't share processes).
Significance: This demonstrates that OPDL is not limited to process algebras but applies to high-level coordination languages where concurrency is implicit.

5. Significance and Future Work

Unification: OPDL provides a general framework that subsumes various previous extensions of PDL (like $\pi$ -DL or CCS-based logics) as specific instantiations of the operational axiom.
Expressivity: It overcomes the "undecidability wall" of interleaving by moving the complexity of trace generation into the operational semantics parameter, allowing the logic to reason about complex features like recursion, replication, and dynamic process creation.
Proof Theory: The cut-elimination result for non-wellfounded calculi is a significant contribution to proof theory, applicable beyond just PDL.
Applications:
- Formal Verification: Enables the use of dynamic logic for verifying concurrent systems with rich features.
- Hoare Logic: OPDL naturally encodes Hoare triples ( $\{P\}\alpha\{Q\}$ as $P \to [\alpha]Q$ ), generalizing Hoare logic for choreographies.
- Endpoint Projection: Offers a potential unifying framework for proving the correctness of compiling choreographies to distributed code.
Limitations & Future Directions: The authors note that the decision problem for OPDL is generally undecidable (as it captures trace equivalence for non-regular languages). Future work involves investigating decision procedures for specific subclasses of operational semantics and extending the framework to the full $\pi$ -calculus and higher-order choreographies.

In summary, the paper successfully bridges the gap between dynamic logic and concurrency by introducing a parameterized logic (OPDL) that separates program syntax from trace semantics, backed by a rigorous cut-elimination proof, and validated through complex case studies in process algebras and choreographic programming.