💻 computer science

TREBL -- A Relative Complete Temporal Event-B Logic. Part I: Theory

This paper introduces TREBL, a relative complete temporal logic for Event-B that expresses liveness properties over state traces, defines sound derivation rules for it, and proves that valid entailments can always be derived given sufficiently refined machines where specific variant terms are definable.

Original authors: Klaus-Dieter Schewe, Flavio Ferrarotti, Peter Rivière, Neeraj Kumar Singh, Guillaume Dupont, Yamine Aït Ameur

Published 2026-04-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Klaus-Dieter Schewe, Flavio Ferrarotti, Peter Rivière, Neeraj Kumar Singh, Guillaume Dupont, Yamine Aït Ameur

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 the architect of a very complex, self-driving factory. You have written the blueprints (the code) for how machines move, how robots assemble parts, and how security guards check IDs. You know the blueprints are logically sound—no machine will ever try to walk through a wall because the math says it can't.

But there's a bigger worry: Will the factory ever get stuck? Will a robot get stuck waiting for a part that never arrives? Will a security guard get stuck waiting for a door that never opens? In computer science, we call these "liveness" problems. We want to prove that the system doesn't just not crash, but that it actually keeps moving forward.

This paper introduces a new, super-powered tool called TREBL (Temporal Event-B Logic) to solve exactly this problem. Here is how it works, explained without the heavy math jargon.

1. The Old Problem: Looking at the Wrong Thing

Traditionally, to prove a factory won't get stuck, you had to look at every possible path the factory could take. Imagine trying to watch every single possible movie that could ever be made with your actors. It's impossible. You'd have to trace every single step of every possible timeline.

Previous tools tried to do this by treating time as a separate, complicated layer. They said, "Let's look at the whole movie script." This made the logic very hard to use and often impossible to prove completely.

2. The New Idea: The Crystal Ball

The authors of this paper had a brilliant insight: You don't need to watch the whole movie to know how it ends.

In their system (Event-B), the current state of the factory (where the robots are, what the doors are doing) acts like a Crystal Ball. If you know exactly where everything is right now, the blueprints determine exactly what can happen next. The future is already "baked in" to the present state.

TREBL changes the game by saying: "Let's stop looking at the whole timeline. Let's just look at the current state and ask, 'Does this state guarantee a good future?'"

Instead of writing complex rules about "forever" or "eventually," TREBL treats these time concepts as shortcuts. It translates "The robot will eventually get a part" into a simple math question about the robot's current position and a special "energy meter."

3. The Secret Weapon: The "Energy Meter" (Variants)

How do we prove the robot will eventually get the part? The paper introduces the concept of a Variant, which is like an Energy Meter or a Countdown Timer.

Imagine the robot is stuck in a loop. To prove it will escape, you need a rule that says: "Every time the robot tries to move, its Energy Meter goes down by 1."

If the meter starts at 100, and it goes down every step, it must eventually hit 0.
When it hits 0, the robot is no longer stuck; it has reached its goal.

The paper proves a magical thing: If a system is supposed to work (it's "live"), you can always find a way to build this Energy Meter into the blueprints. You might need to add a few extra variables (like a counter) to the design, but it's always possible. This is called Relative Completeness. It means: "If the system is correct, our tools can always prove it, as long as you give us the right Energy Meter."

4. Handling the Chaos: Security and Fairness

The paper also tackles tricky scenarios, like Security (Non-interference).

The Problem: Can a high-level spy see what a low-level worker is doing?
The TREBL Solution: Instead of tracing every possible spy scenario, TREBL looks at the current state and asks, "If a high-level event happens, does it change the low-level worker's view?" It turns a complex security puzzle into a simple "before and after" math check.

It also handles Fairness. If a worker is waiting for a turn, does the system guarantee they get it? TREBL uses the Energy Meter to prove that the system can't keep ignoring the worker forever without the "meter" running out.

5. The Big Picture: Why This Matters

Think of previous methods as trying to solve a maze by walking every single path until you find the exit. It's slow and sometimes you get lost.

TREBL is like having a map that shows you the exit is reachable if you just follow the "downhill" path (the Energy Meter).

It's simpler: You don't need to think about "time" as a separate dimension; you just look at the current state.
It's complete: The authors proved that if a solution exists, this method can find it.
It's practical: They showed examples using security systems and production lines, proving that even complex safety rules can be checked easily with this new logic.

Summary Analogy

Imagine you are playing a video game.

Old Way: To prove you can beat the level, you have to simulate every possible move the game could make, every enemy path, and every glitch, hoping you don't get stuck.
TREBL Way: You look at your character's current health and ammo. You define a rule: "Every time you take a step, your health drops by 1." Since health can't go below zero, you know you must reach the end of the level eventually. You don't need to simulate the whole game; you just need to prove the "Health Drop" rule exists.

This paper builds the ultimate rulebook for proving that complex, automated systems will keep working and never get stuck, using simple math instead of impossible simulations.

1. Problem Statement

The verification of liveness conditions (e.g., progress, fairness, termination) in rigorous state-based methods like Event-B, B, or TLA+ presents a fundamental challenge.

Expressiveness vs. Completeness Trade-off: Classical temporal logics (LTL, CTL) are complete but are propositional, limiting their expressiveness when applied to systems with complex state variables. Extending these logics to first-order logic increases expressiveness but typically results in incompleteness (no sound and complete proof system exists).
Trace Interpretation: Traditional approaches interpret temporal formulas over traces (sequences of states). However, in state-based methods, a specific state determines all possible future traces. Interpreting formulas over traces rather than states complicates the logic and prevents relative completeness.
Limitations of Previous Work: Previous attempts to integrate LTL with Event-B (e.g., by Hoang & Abrial, and later Ferrarotti et al.) achieved soundness but failed to achieve relative completeness without restrictive assumptions (specifically, the "tail-homogeneity" of traces). They also retained the complexity of trace-based interpretation.

2. Methodology

The authors propose TREBL (Temporal Event-B Logic), a fragment of an extended Event-B logic designed to overcome these limitations. The methodology relies on three core pillars:

A. Logic Extension ( $L_{ext}$ ) via Update Sets

Instead of treating traces as external sequences, the authors extend the standard Event-B logic ( $L$ ) to an extended logic ( $L_{ext}$ ) where:

Update Sets: The effect of firing an event is explicitly modeled as an "update set" (a set of variable-value pairs).
Multi-step Composition: The logic supports the inductive definition of update sets for multiple steps ( $k$ steps), allowing the expression of properties over sequences of states without leaving the first-order framework.
Modal Operators as Shortcuts: Temporal operators (Always $\square$ , Eventually $\diamond$ , Until $U$ ) are defined as syntactic shortcuts for complex formulas in $L_{ext}$ .
State-Based Interpretation: Crucially, all formulas in $L_{ext}$ (and thus TREBL) are interpreted over states, not traces. A state formula $\phi$ holds if it holds in the initial state of the traces it generates. This leverages the property that a state in Event-B determines its future traces.

B. Definition of TREBL

TREBL is defined as the closure of the Event-B logic under specific temporal constructors:

Invariance: $\square \phi$ (holds in all traces).
Existence: $\square \diamond \phi$ (eventually holds in all traces).
Progress: $\square (\phi \rightarrow \diamond \psi)$ (if $\phi$ holds, $\psi$ eventually follows).
Persistence: $\diamond \square \phi$ (eventually $\phi$ holds forever).
Variants: The logic includes "one-trace" analogues (e.g., $\square_1 \phi$ , $\diamond_1 \phi$ ) and quantification over definable sets of traces (inspired by Team Semantics), allowing for more flexible security property definitions.

C. Derivation Rules and Variant Terms

To prove liveness properties, the authors introduce a set of derivation rules that rely on variant terms:

Variant Terms: Terms mapping states to a well-founded set (e.g., natural numbers) that strictly decrease under specific conditions.
Types of Variants:
- c-variants: For convergence (existence).
- d-variants: For divergence (persistence).
- e-variants: For reachability.
- Simultaneous/Conditional Variants: Complex pairs of terms used to handle progress conditions and mixed trace quantifiers.
Refinement Strategy: The authors prove that for any valid liveness property, there exists a conservative refinement of the Event-B machine where the necessary variant terms can be explicitly defined. This is the key to achieving relative completeness.

3. Key Contributions

Definition of TREBL: A formal logic that integrates temporal operators into Event-B while maintaining a state-based interpretation, avoiding the complexity of explicit trace quantification in the semantics.
Soundness and Relative Completeness:
- The authors provide a sound set of derivation rules for TREBL.
- They prove relative completeness: If a machine $M$ satisfies a TREBL formula $\phi$ , and $M$ is "sufficiently refined" (i.e., contains the necessary variant terms), then $\phi$ is derivable using the provided rules.
Removal of Tail-Homogeneity Restriction: Unlike previous work, this approach removes the requirement that traces must be "tail-homogeneous" (where all traces behave similarly regarding the liveness condition). This is achieved by using definable sets of traces and conditional variants.
Handling of One-Trace and Team Semantics: The logic supports formulas that must hold in some trace ( $\square_1, \diamond_1$ ) or over specific subsets of traces, enabling the expression of complex security properties like non-interference and bounded deducibility.
Security Applications: The paper demonstrates the application of TREBL to security problems (e.g., non-interference in multi-level stacks, bounded deducibility), showing that complex hyperproperties can be expressed as simple invariance conditions with state transitions.

4. Results

Theoretical Proof: The paper provides rigorous proofs for the soundness of 63 derivation rules covering invariance, existence, persistence, and progress (both all-trace and one-trace variants).
Existence of Refinements: A critical result is the proof (via Lemmas 2.4, 2.6, 2.8, 2.10, 2.14, 2.17, 2.20, 2.22) that for any valid liveness property, a conservative refinement exists that defines the required variant terms. This guarantees that the "relative" aspect of completeness is always satisfiable.
Case Studies:
- Non-Interference: Expressed as a simple invariance condition ( $\square \phi$ ) rather than a complex hyperproperty.
- Producer-Consumer: Demonstrated the proof construction for progress (guaranteed service) and persistence (eventual stability) using the derived rules and lexicographic variants.

5. Significance

Bridging the Gap: TREBL successfully bridges the gap between the expressiveness of first-order temporal logic and the mechanical verifiability of state-based methods. It solves the "Scylla and Charybdis" dilemma (expressiveness vs. completeness) for Event-B.
Practical Verification: By shifting the interpretation to states and using refinement to introduce variants, the logic makes the verification of complex liveness properties (like fairness and termination) feasible within existing toolchains (specifically the RODIN tool with EB4EB meta-theory, as mentioned for Part II).
Generalizability: While focused on Event-B, the methodology (using update sets and state-based interpretation) is applicable to other rigorous methods like Abstract State Machines (ASMs), B, and TLA+.
Foundation for Tooling: This theoretical Part I lays the groundwork for Part II, which focuses on the practical implementation and automation of these proofs in the RODIN platform.

In summary, the paper establishes a robust theoretical foundation for verifying liveness in Event-B systems, proving that with appropriate refinements, a sound and relatively complete temporal logic is achievable, thereby significantly enhancing the verification capabilities of rigorous state-based methods.