💻 computer science

A Correct Algorithm for Identifying Independent Variable Sets in Reactive Systems

This paper provides a rigorous semantic analysis of the DecomposeContract algorithm for decomposing reactive synthesis specifications, identifies its incompleteness through a counterexample, and proposes a refined, complete decomposition procedure that leverages model checking to identify independent variable sets.

Original authors: Josu Oca, Montserrat Hermo, Alexander Bolotov

Published 2026-06-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Josu Oca, Montserrat Hermo, Alexander Bolotov

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 build a complex robot that needs to react to a chaotic environment. You have written a massive, complicated rulebook (a "specification") for how this robot should behave. The problem is that this rulebook is so huge and tangled that figuring out if the robot can actually follow the rules is incredibly difficult—like trying to solve a giant jigsaw puzzle where the pieces keep changing shape.

This paper is about a new, smarter way to untangle that rulebook.

The Problem: A Tangled Knot

The authors are looking at "Reactive Systems"—think of them as robots or software that constantly interact with the outside world. The outside world (the "environment") throws things at the robot, and the robot (the "system") has to respond.

To make sure the robot works, we write a logical formula (a set of rules). But these rules are often a mess. If you have 100 variables (like "is the door open?", "is the light on?", "is the battery low?"), checking if the robot can satisfy all 100 rules at once is computationally impossible for current computers in many cases.

The Old Solution: A Good, But Flawed, Map

A few years ago, researchers proposed a clever trick called DC. Instead of checking the whole mess at once, they tried to break the rulebook into smaller, independent chunks.

The Analogy: Imagine you are trying to organize a messy closet. The old method (DC) says: "Let's pick one shirt. Is it independent of the rest? If not, let's grab another shirt that seems related and check them together. Keep adding shirts until the group feels 'complete'."

The authors of this paper found that the old method was sound (it never gave a wrong answer) but incomplete (it missed the best way to split things up).

The Flaw: Sometimes, the old method would grab a whole pile of clothes and say, "These are all stuck together," when in reality, the pile could have been split into two neat, separate stacks. It was too lazy to find the perfect separation.

The New Solution: The "Detective" Algorithm (NDC)

The authors, Josu Oca, Montserrat Hermo, and Alexander Bolotov, revisited this method. They didn't just tweak the code; they built a rigorous mathematical foundation to understand why things were independent or dependent.

They introduced a new algorithm called NDC.

How it works (The Detective Metaphor):
Imagine the old method was a detective who just asked, "Are these two suspects working together?" and if the answer was "maybe," they arrested both.
The new method (NDC) is a super-detective. When the computer finds a "counterexample" (a scenario where the rules break), NDC doesn't just grab the suspects. It interrogates the evidence.

It looks at the specific moment the rules failed.
It asks: "Which specific variables caused this failure?"
Crucially, it checks if those variables are truly stuck together or if they just looked stuck because of a third variable.
It uses a "model checker" (a powerful tool that simulates scenarios) to test these hypotheses.

The Result:
NDC guarantees that when it splits the rulebook into groups, those groups are minimal.

Old Way: "Here is a group of 5 variables. They are independent." (But maybe 3 of them could have been a separate group, and the other 2 another group).
New Way: "Here is a group of 2 variables. They are independent. And here is another group of 3. They are independent. We couldn't have split them any further."

Why This Matters

The paper proves that this new method is complete. In plain English, it means the algorithm will always find the finest possible way to break down the problem. It won't miss a hidden opportunity to split the work into smaller, easier pieces.

The Catch (The "Reality Check")

The authors are very honest about the limits of their work.

The Setting: Their method works perfectly for checking if a set of rules is satisfiable (i.e., "Is there any way to make this work?").
The Limit: In the real world of building robots, we don't just want to know if it's possible; we need to know if the robot can win against a tricky environment (this is called "realizability").
The Conclusion: The authors say that while their method is great for finding independent variables in the "possibility" sense, applying it to the "winning strategy" sense is much harder. It's like the difference between asking "Can this car drive on this road?" (easy) vs. "Can this car drive on this road while avoiding a driver who is trying to crash into it?" (much harder). They suggest that finding the perfect split for the "winning strategy" problem might be just as hard as solving the whole problem in the first place.

Summary

This paper takes a good idea (breaking big logic problems into small ones), fixes a hole in the logic that caused it to miss the best solutions, and provides a mathematically proven, "perfect" way to do it. It's like upgrading from a rough sketch of a map to a GPS that guarantees you've found the absolute shortest route to break down a complex task.

Technical Summary: A Correct Algorithm for Identifying Independent Variable Sets in Reactive Systems

Problem Statement

Reactive synthesis, the automatic construction of systems that satisfy Linear Temporal Logic (LTL) specifications against all possible environment behaviors, is a computationally hard problem (2EXPTIME-complete). To address scalability, a common strategy is to decompose a complex specification into smaller, independent subspecifications that can be solved separately.

The paper revisits the DecomposeContract (DC) algorithm introduced by Iannopollo (2018) and Iannopollo et al. (2024). This algorithm uses a model checker to identify sets of system-controlled variables that behave independently within an LTL formula. While the original DC algorithm is sound (any set it identifies as independent is indeed independent), it is not complete. It may fail to detect finer decompositions, returning a single large set of dependent variables when a partition into smaller independent sets exists. This limitation hinders the full exploitation of decomposition for improving synthesis scalability.

Methodology and Semantic Foundations

1. Semantic Analysis of Independence

The authors provide a rigorous semantic analysis of the independence notion used in DC. They formalize independence using concepts from relational algebra, specifically projection and join operators applied to sets of traces.

Trace Projection ( $\sigma \upharpoonright V$ ): Restricts a trace to a subset of variables $V$ while preserving environment variables.
Join ( $\Sigma_1 \bowtie \Sigma_2$ ): Combines sets of traces over different variable subsets into a set of traces over their union, provided the traces agree on the intersection.
Join-Independence: A set of system variables $V \subseteq O$ is defined as independent in a formula $\phi$ if and only if the join of the projections of the model set $\Sigma_\phi$ onto $V$ and its complement $\bar{V}$ reconstructs the original model set:
$(\Sigma_\phi \upharpoonright V) \bowtie (\Sigma_\phi \upharpoonright \bar{V}) = \Sigma_\phi$
The authors prove that this semantic definition is equivalent to the syntactic validity condition used in the original DC algorithm: $(\phi_V \land \phi_{\bar{V}}) \to \phi$ is valid.

2. The Limitation of the Original DC Algorithm

The original DC algorithm builds independent sets incrementally. Starting with a single variable, it checks if the current set $V$ is independent. If the validity check fails, the model checker returns a counterexample trace. The algorithm then analyzes this trace to find variables whose values differ from their "primed" (fresh) counterparts in the projection, adding them to $V$ .

The paper demonstrates that this approach is incomplete because it relies on a direct check between the current set and the remaining variables. It fails to account for mediated dependencies. As shown in Example 11, a variable $b$ might be dependent on a set only when considered alongside a third variable $a$ , even if the direct interaction between $b$ and the rest of the set does not immediately reveal this dependency. Consequently, DC may prematurely conclude that a set is independent or fail to merge necessary variables, resulting in non-minimal independent sets.

3. The Proposed Solution: NDC Algorithm

To achieve completeness, the authors propose NDC (New DecomposeContract). The core modification lies in the ParseTrace function, replaced by NewParseTrace.

Refined Dependency Detection: When the validity check fails, NewParseTrace does not simply add all variables that differ in the counterexample. Instead, it iteratively constructs a formula binds that accumulates constraints ( $\Diamond(z \leftrightarrow \neg z')$ ) on variables found to be dependent.
Iterative Refinement: The algorithm queries the model checker with a disjunction: binds $\lor$ ((\phi_V \land \phi_{\bar{V}}) \to \phi). If this formula is invalid, the model checker provides a new trace where the current binds constraints are violated, revealing a new variable $z$ that must be added to the set.
Theoretical Guarantee: The algorithm relies on Lemma 6, which establishes that if a set $V$ is dependent within a larger independent superset $W$ , then any variable $q \in W$ cannot "witness" the independence of $V$ unless the dependency is explicitly exposed through the accumulation of constraints. This ensures that the algorithm continues to expand the set until it reaches a minimal independent set.

Key Contributions and Results

Mathematical Formalization: The paper provides the first rigorous semantic account of the independence notion used in Iannopollo's work, defining it via trace projections and joins. This clarifies the theoretical underpinnings of the decomposition method.
Proof of Incompleteness: The authors present a concrete counterexample (Example 6 and Example 11) demonstrating that the original DC algorithm is not complete and can miss valid decompositions.
Correct and Complete Algorithm (NDC): The paper introduces NDC, a refined algorithm that preserves the polynomial-time nature of the original method (excluding model checker costs) while ensuring completeness.
Minimality Guarantee: The primary theoretical result (Theorem 1) proves that NDC returns a partition of system variables into minimal independent sets. This means that if a set is returned as independent, no non-empty proper subset of it is itself independent. This is a stronger guarantee than the original DC, which only guarantees soundness.
Limitations in Realisability: The paper explicitly distinguishes between satisfiability (where traces are the semantic objects) and realisability (where winning strategies are the semantic objects). The authors note that while NDC is complete for identifying independence in the satisfiability setting, extending these results to the realisability setting is significantly more challenging. In the realisability setting, the set of traces induced by winning strategies is a subset of all satisfying traces, and the minimality of the decomposition is not guaranteed to be computable with the same efficiency as the satisfiability-based approach.

Significance and Claims

The paper claims that its main contribution is theoretical, providing a rigorous foundation for decomposition methods in reactive synthesis. By clarifying the semantics of independence and correcting the algorithmic procedure, the authors enable the reliable decomposition of LTL specifications into minimal independent components.

The significance lies in:

Correctness: Ensuring that decomposition does not miss opportunities to split specifications, which is crucial for the scalability of synthesis tools.
Efficiency: Maintaining the practical efficiency of using model checkers (which are highly optimized) rather than resorting to expensive automata-theoretic operations like complementation.
Clarity: Explicitly delineating the boundaries of the method, particularly the distinction between satisfiability-based independence and strategy-based independence, preventing over-optimistic expectations regarding the direct application of these results to the full realisability problem.

The work does not propose new experimental benchmarks or future tool implementations but focuses on establishing the mathematical correctness and completeness of the decomposition logic itself.