💻 computer science

On A Parameterized Theory of Dynamic Logic for Operationally-based Programs

The paper introduces DLp, a novel, parametric dynamic logic framework that simplifies program verification by providing a model-independent set of inference rules directly based on a program's operational semantics, supporting both cyclic reasoning and compatibility with existing theories.

Original authors: Yuanrui Zhang

Published 2026-02-11

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Yuanrui Zhang

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 teach a robot how to navigate a complex, ever-changing obstacle course.

Currently, most "instruction manuals" (which computer scientists call Dynamic Logics) for these robots are written in a way that assumes the course is static. To use these manuals, you often have to rewrite the robot's entire map or transform the obstacle course into a "standard" version before the robot can even start. This is tedious, prone to errors, and sometimes impossible if the course is too chaotic.

This paper introduces a new manual called $\text{DL}_{\mathfrak{p}}$ . Here is the breakdown of how it works using a few simple analogies.

1. The "GPS with Live Traffic" (Operational Semantics)

Traditional logic is like a printed map: it tells you where you start and where you end up, but it doesn't care about the turns you take in between. If the road changes, the map is useless.

$\text{DL}_{\mathfrak{p}}$ is like Google Maps with live GPS: it doesn't just look at the destination; it follows the actual "turns" (the operational semantics) the program takes step-by-step. Because it follows the actual movement, you don't have to redesign the manual every time you change the robot; you just plug in the new "turn-by-turn" directions.

2. The "Sticky Note" System (Labeling and Parameterization)

In old systems, if you wanted to track a variable (like the robot's battery level), you had to bake that information into the very foundation of the logic. It was like trying to write a book where every page is permanently glued to a specific temperature.

$\text{DL}_{\mathfrak{p}}$ uses "Sticky Notes" (Labels). Instead of changing the whole book, you just slap a sticky note on a page that says, "Current Battery: 80%." As the robot moves, you peel off the old note and slap on a new one: "Current Battery: 75%." This makes the logic "parameterized"—meaning the core rules stay the same, and you just swap out the sticky notes depending on what you are tracking.

3. The "Infinite Loop" Problem (Cyclic Reasoning)

Imagine a robot tasked with walking in a circle forever. A traditional logic manual would get stuck in an infinite loop trying to prove what happens, because it keeps trying to reach a "final destination" that never comes. It’s like a mathematician trying to count to infinity—they’ll never finish the proof.

$\text{DL}_{\mathfrak{p}}$ uses "Cyclic Reasoning." Instead of trying to count to infinity, the manual says: "Wait, I've seen this exact situation before! I'm back at the same spot with the same sticky note. Since I know what happened the last time I was here, I can conclude that the pattern will continue safely." It recognizes the "loop" and closes the book, rather than getting lost in it.

Summary: Why does this matter?

In the real world, software is getting incredibly complex—think of blockchain, quantum computers, or self-driving cars. These systems don't follow simple "start-to-finish" paths; they react, loop, and change constantly.

The "Big Win" of this paper is flexibility. By creating a framework that follows the actual "steps" of a program and uses "sticky notes" to track data, the author has created a universal toolkit. You can use the same basic logic to verify a simple calculator, a complex web of communicating processes, or even a futuristic quantum computer, without having to reinvent the wheel every single time.

Technical Summary: On A Parameterized Theory of Dynamic Logic for Operationally-based Programs

1. Problem Statement

Traditional program verification frameworks, such as Hoare logic and standard Dynamic Logics (DL), are primarily built upon denotational semantics. In these models, a program's behavior is interpreted as a mathematical object (e.g., a set of traces). While powerful, this approach poses several challenges:

Adaptation Difficulty: Adapting existing logics to new or complex programming languages (like Java or C) requires designing and validating a massive set of new axiomatic rules, which is error-prone and costly.
Transformation Overhead: To apply standard rules, programs often must be transformed into "standard forms" (e.g., converting synchronous programs into STA programs), which can lead to a loss of program information.
Complexity of Semantics: For modern or concurrent models, the operational semantics (how a program transitions step-by-step) is often more readily available and trusted than the denotational semantics.

2. Methodology

The author proposes $\text{DL}_{\mathfrak{p}}$ , a novel, parameterized dynamic logic designed to reason directly using a program's structural operational semantics. The methodology is built on three core pillars:

Labeling and Parameterization: $\text{DL}_{\mathfrak{p}}$ introduces "labels" ( $\sigma$ ) to capture explicit program configurations (e.g., current variable values, heap states, or substitutions) during symbolic execution. A formula is represented as $\sigma: [\alpha]\phi$ , meaning "under configuration $\sigma$ , after executing program $\alpha$ , formula $\phi$ holds." This allows the logic to be model-independent; the framework remains the same while the program model ( $\alpha$ ) and the logical formula ( $\phi$ ) are treated as parameters.
Cyclic Proof System: To handle recursive programs and infinite symbolic executions (e.g., while loops), the paper employs a cyclic proof approach. Instead of requiring finite proof trees, $\text{DL}_{\mathfrak{p}}$ allows for "buds" (non-terminating leaf nodes) that link back to their ancestors. The author introduces a "progressive derivation trace" to ensure that these cycles are logically sound and do not represent invalid infinite loops.
Lifting Process: To ensure compatibility with existing theories (like First-Order Dynamic Logic - FODL), the author develops a "lifting" technique. This allows existing, domain-specific inference rules to be embedded into the $\text{DL}_{\mathfrak{p}}$ framework by attaching "free labels," thereby combining the efficiency of specialized rules with the generality of the new framework.

3. Key Contributions

A New Logical Framework: Defined the syntax and semantics of $\text{DL}_{\mathfrak{p}}$ using a novel "program-labeled Kripke structure."
A Labeled Proof System ( $Pr_{\text{dlp}}$ ): Developed a kernel set of inference rules that are independent of specific program structures, relying instead on a parameter of rules ( $\text{Prop}$ ) that describes the program's transitions.
Cyclic Reasoning Mechanism: Proposed a specialized cyclic derivation approach that enables incremental reasoning for recursive programs without prior program transformations.
Formal Verification of the Logic: Provided mathematical proofs for the soundness and completeness of the $\text{DL}_{\mathfrak{p}}$ system under specific conditions (Termination Finiteness and Well-behaved Loop Programs).

4. Results and Case Studies

The paper demonstrates the versatility of $\text{DL}_{\mathfrak{p}}$ through several instantiations:

$\text{DL}_{\mathfrak{p}}\text{-WP}$ : Successfully derived properties of "while programs" using cyclic proofs, showing how the loop structure is naturally reflected in the derivation.
$\text{DL}_{\mathfrak{p}}\text{-FODL}$ : Demonstrated the ability to embed and lift traditional first-order rules, proving the framework's compatibility with established logics.
$\text{DL}_{\mathfrak{p}}\text{-PL}$ (Process Logic): Showed that by using more complex labels (sequences of configurations) and temporal formulas, $\text{DL}_{\mathfrak{p}}$ can reason about reactive systems and properties that hold during execution, rather than just at termination.
Heterogeneity: Demonstrated that different program models (e.g., regular programs vs. while programs) can be compared within a single framework.

5. Significance

This work is significant because it shifts the burden of program verification from re-designing logic rules to providing operational transitions. By leveraging the operational semantics that developers already use to define languages, $\text{DL}_{\mathfrak{p}}$ provides a more direct, flexible, and scalable path for verifying diverse software models—ranging from standard imperative code to complex synchronous and reactive systems. It bridges the gap between high-level logical reasoning and low-level operational execution.