💻 computer science

Labelled Process Logic

This paper introduces a uniform cyclic labelled proof-theoretic framework, comprising the systems G3PPL and G3FOPL, that achieves a complete treatment of both propositional and first-order process logic by enriching formulas with labels to explicitly track trace and update information during derivations.

Original authors: Yuanrui Zhang

Published 2026-06-10

📖 5 min read🧠 Deep dive

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 prove that a robot will never crash while navigating a maze.

In the old way of doing things (called "Dynamic Logic"), you would only check the robot's final destination. You'd ask: "If the robot starts here and follows these instructions, will it end up in the safe zone?" This is like checking a map only at the finish line. It tells you if you arrived, but not if you drove off a cliff on the way there.

Process Logic is an upgrade. It cares about the entire journey. It asks: "Did the robot stay on the road, avoid the cliffs, and follow the rules at every single step of the trip?" This is much harder to prove because you have to track the robot's entire history, not just its final stop.

The paper by Yuanrui Zhang introduces a new, powerful tool called Labelled Process Logic to solve this difficult math problem. Here is how it works, using simple analogies:

1. The Problem: The "Splitting" Nightmare

Imagine you are trying to prove a robot can safely drive through a long tunnel made of two sections: Section A and Section B.

In traditional math proofs, to prove the whole trip is safe, you often have to "split" the problem. You try to prove Section A is safe, then prove Section B is safe, and then try to glue the two proofs together.
The problem is that the "glue" is messy. If the robot's path in Section A changes how Section B behaves, the math gets incredibly complicated. Existing tools could handle simple tunnels, but they broke down when the tunnels got complex, looped back on themselves, or had many possible paths.

2. The Solution: The "Backpack" (Labels)

The author's big idea is to stop trying to glue the pieces together at the end. Instead, give the proof a backpack (called a "Label").

How it works: As the proof moves through the robot's instructions, it doesn't just write down "Is this safe?" It writes down "We are at step 5, the robot turned left, and the battery is at 80%."
The Magic: This "backpack" (the label) carries the history of the journey inside the proof itself.
- Instead of splitting the problem into two hard pieces, the proof just adds the new step to the backpack.
- If the robot does Step A then Step B, the proof simply updates the backpack to say History: Step A + Step B.
- This makes the math much cleaner. You don't need complex rules to "glue" things; you just keep adding to the list of what happened.

3. The Loop Problem: The "Infinite Hallway"

Computers and robots often have loops (e.g., "Keep driving until you see a red light").

If you try to prove a loop using standard math, you might get stuck in an infinite hallway. You prove step 1, then step 2, then step 3... and since the loop repeats, you never reach the end of the proof.
The Cyclic Fix: The author allows the proof to "loop back on itself." Imagine a proof that looks like a snake eating its own tail.
- The proof says: "I am at step 10. I know I was at step 1 before. Since the rules are the same, I can jump back to step 1 and say, 'I've already checked this part, so I'm good.'"
- The Safety Check: To make sure this isn't cheating, the author adds a rule: Every time the proof loops back, it must prove that the "backpack" (the label) has changed in a specific, shrinking way. It's like a game where you can only loop back if you have fewer cookies left in your jar. Eventually, you run out of cookies, proving the loop is safe and finite.

4. Two Versions of the Tool

The paper builds two versions of this system:

G3PPL (The Simple Version): Works for abstract logic puzzles where you just care about "True" or "False" states. It uses labels to track simple paths.
G3FOPL (The Advanced Version): Works for real-world math involving numbers and variables (like x = x + 1). Here, the "backpack" doesn't just track the path; it tracks updates. If the robot changes a number, the label records that change explicitly (e.g., "x is now 5"). This allows the system to handle real computer programs with math inside them.

The Bottom Line

The paper claims to have built the first complete, reliable math framework that can prove properties about entire execution paths of complex computer programs, including loops and loops with math.

Before: We could only easily prove where a program ends, or handle very simple paths.
Now: We have a unified system (using "backpacks" and "safe loops") that can prove complex, step-by-step behaviors for both simple logic and complex math-based programs.

The author proves this system is Sound (it never lies; if it says a program is safe, it really is) and Complete (it can prove anything that is actually true). This is a major step forward in making sure software behaves exactly as we expect it to, from the first second to the last.

Technical Summary: Labelled Process Logic

1. Problem Statement

Process Logic (PL) extends Dynamic Logic (DL) by shifting the focus from reasoning about final program states to reasoning about entire execution traces. While the propositional theory of Process Logic (PPL) is well-understood regarding decidability and completeness, the first-order extension (FOPL) presents significant challenges.

The core difficulty lies in the compositional reasoning required for first-order process logic over regular programs. In standard Dynamic Logic, a formula $[\alpha]\phi$ asserts that every terminating execution of $\alpha$ ends in a state satisfying $\phi$ . In Process Logic, $[\alpha]\pi$ asserts that every execution trace of $\alpha$ satisfies a temporal property $\pi$ (expressed via Linear Temporal Logic operators like next, always, eventually, and until).

Existing compositional calculi for fragments of this logic (e.g., Beckert's sequent calculus for deterministic while programs, or extensions like DLT and DTL) fail to provide a complete treatment for full first-order process logic over regular (potentially non-deterministic) programs. Specifically:

Compositional rules for sequential programs (splitting a trace property $\pi$ across $\alpha; \beta$ ) often depend heavily on the specific shape of the temporal formula (e.g., specific rules for "always" vs. "eventually").
Some proposed rules are insufficient for general regular programs because tests in sequential compositions can block traces, invalidating simple compositional splits.
No existing system offers a uniform framework where trace-based properties and first-order computations are handled within the same proof structure for the full logic.

2. Methodology: Cyclic Labelled Proof Systems

The paper proposes a novel proof-theoretic framework that enriches process logic formulas with labels to explicitly record execution information during derivations, rather than relying on increasingly complex compositional rules.

2.1 Labelled Formulas

The authors introduce labelled formulas of the form $\sigma : \phi$ , where:

$\phi$ is a process logic formula.
$\sigma$ $σ$ is a label representing the execution trace or program configuration accumulated so far.
- In Propositional Process Logic (PPL), labels are traces of worlds ( $\sigma \in L$ ), constructed from world variables, trace variables, and concatenation.
- In First-Order Process Logic (FOPL), labels are enriched with program updates ( $U$ ) to record the cumulative effect of assignments (e.g., $\{u := e\}$ ) over an arithmetic structure.

This approach makes intermediate execution information available inside the proof system. Consequently, the proof system no longer needs to split sequential traces using special-purpose temporal rules at the point of sequence; instead, it unfolds the program structure while accumulating information in the label.

2.2 Cyclic Proof Structure

Since regular programs include iteration ( $\alpha^*$ ), proof search may generate infinite derivations. To handle this, the authors adopt cyclic proof theory.

Preproofs: Finite trees where leaf nodes (buds) can "back-link" to ancestor nodes with identical syntactic forms (modulo variable renaming).
Cyclic Condition: To ensure soundness, not all cycles are valid. The paper defines a progressive derivation trace. A derivation is a valid cyclic proof if every infinite path contains a "progressive step" (e.g., applying a rule that reduces the complexity of the trace or formula).
Soundness Mechanism: The authors prove soundness by showing that any infinite derivation path satisfying the cyclic condition induces an infinite descent in a well-founded multiset ordering of "minimal counter-example traces." This contradiction ensures that no invalid formula can be proved.

2.3 The Proof Systems

Two specific systems are defined:

G3PPL: A cyclic labelled proof system for Propositional Process Logic. It extends labelled sequent techniques for modal logics, adapting them to trace semantics.
G3FOPL: A cyclic labelled proof system for First-Order Process Logic. It extends G3PPL by replacing atomic program rules with rules for assignments (updating the label) and adding standard first-order quantifier rules.

3. Key Contributions

The paper makes the following specific contributions:

Labelled Formulas: The introduction of trace labels for PPL and update-based labels for FOPL, allowing execution history to be tracked explicitly within the proof structure.
Cyclic Labelled Systems: The definition of G3PPL and G3FOPL, which share a common labelled framework but utilize rules specific to propositional and first-order process logic, respectively.
Soundness Proofs: A proof of soundness for both systems. The argument relies on reducing every progressive infinite derivation path to an infinite descent in a well-founded multiset ordering of minimal counter-example traces.
Completeness Proofs:
- For G3PPL, completeness is established by demonstrating that the labelled system can derive every axiom and rule of the established Hilbert-style proof system for PPL.
- For G3FOPL, completeness is established by adapting the classical completeness argument for First-Order Dynamic Logic (FODL) to the trace-based setting, utilizing arithmetical encodings.

4. Results

Uniform Framework: The paper successfully constructs a uniform framework where trace-based program properties and first-order computations are handled within the same proof structure.
Completeness for Regular Programs: The systems provide the first complete logical framework for full first-order process logic over regular programs (including non-deterministic choice and iteration).
Soundness and Completeness: Both G3PPL and G3FOPL are proven to be sound and complete with respect to their respective semantics.

5. Significance

The paper claims that this work addresses a long-standing gap in the literature. Previous systems either:

Were limited to deterministic programs (e.g., DLT, DTL).
Lacked completeness for general regular programs.
Could not uniformly handle all LTL operators (e.g., until) in the presence of non-determinism.

By using labels to externalize execution information and cyclic proofs to handle iteration, the authors provide a principled and uniform mechanism for reasoning about trace properties. This allows for the verification of specifications where intermediate behavior is essential, without requiring ad-hoc compositional rules for every temporal operator. The framework unifies the treatment of propositional and first-order levels, offering a robust foundation for program verification involving complex temporal properties.