💻 computer science

Solving Streett and Emerson-Lei Games with Universal Trees

This paper advances the understanding of universal trees by demonstrating their direct applicability to solving Streett and Emerson-Lei games, yielding memory-optimal strategies and improved time complexities that surpass previous methods relying on reductions to parity games.

Original authors: Daniel Hausmann, Marcin Jurdzinski, Nir Piterman

Published 2026-08-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Daniel Hausmann, Marcin Jurdzinski, Nir Piterman

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

In the digital world, many complex problems can be framed as a game between two opponents. One player represents a system we want to build, like a traffic light controller or a robot, while the other represents the unpredictable environment it must survive in. The goal is to determine if the system can always win, no matter how the environment tries to trick it. This is not about luck or chance, but about finding a perfect plan that guarantees success forever. These scenarios are modeled as infinite games where the players take turns moving along a network of paths. The winner is decided by the sequence of moves that happens over and over again. For decades, computer scientists have struggled to find efficient ways to solve these games, especially when the rules for winning are complex and involve remembering past events.

A major breakthrough in this field came with the realization that these games could be solved much faster than previously thought, provided one could find a specific kind of mathematical structure called a universal tree. Think of a universal tree as a master map that contains every possible way a game could unfold, organized in a way that allows a computer to check them all without getting lost in an endless maze. While this idea worked wonders for simpler games, it was widely believed that it could not be applied to more complicated scenarios where the winning strategy required the system to remember its history. The prevailing view was that these memory-heavy games were too messy for such elegant maps to handle.

This paper challenges that long-held belief. The researchers show that universal trees are not just for simple games; they can be combined with another structure, known as a Zielonka tree, to solve the most complex types of games directly. A Zielonka tree acts like a precise instruction manual that tells the system exactly how to use its memory. By weaving these two structures together, the authors have created a new method to solve Streett and Emerson-Lei games, which are used to verify critical systems like safety protocols and automated controllers. Their work proves that these difficult games can be solved significantly faster than before, and crucially, the strategies they produce use the absolute minimum amount of memory required, making them far more efficient than previous methods.

The researchers achieved this by developing a new way to measure progress in these games. Instead of just checking if a player is winning, they assign a rank to every position in the game based on how close it is to victory. In simpler games, this rank is a single number. In these complex games, the rank is a pair of values: one part tracks the position within the universal tree, and the other tracks the specific memory state needed to win. The authors proved that if a player can always move to a position with a lower rank, they have a winning strategy. They showed that for games with a specific number of vertices and edges, this new method calculates the winning regions and the strategies in a time that is much shorter than the old methods, which relied on converting the complex game into a simpler one first.

One of the most significant findings is that this approach does not just solve the game; it produces a strategy that is optimal in its use of memory. Previous methods, which converted these games into simpler ones, often forced the system to carry around unnecessary baggage, using far more memory than was actually needed. The new method extracts a strategy that uses exactly the amount of memory dictated by the rules of the game, no more and no less. This is a vital distinction for building real-world systems, where memory is a limited resource. The paper demonstrates that by understanding the deep structure of these games through the lens of universal and Zielonka trees, one can bypass the inefficiencies of older reduction techniques.

The work also introduces a symbolic algorithm, which is a way of solving the game by manipulating sets of positions rather than checking them one by one. This approach replaces a factor in the time complexity that previously grew very fast with the size of the universal tree, which grows much more slowly. This improvement means that as games get larger, the new method scales much better than the old ones. The authors also show how this technique can be applied to a wide range of conditions, including those used in reactive synthesis, where the goal is to automatically build a system that meets a specific set of requirements.

The paper explicitly refutes the idea that universal trees are only relevant for games where the winning strategy does not need to remember the past. By showing how to integrate memory requirements directly into the ranking system, the authors demonstrate that these trees are a powerful tool for a much broader class of problems. They provide a complete understanding of how these trees interact with the memory structures needed for Streett and Emerson-Lei games. The results are not just theoretical suggestions; they are proven mathematical facts that offer a concrete path to faster and more efficient solutions for verifying complex systems.

In the end, this research bridges a gap that had existed for some time. It takes a powerful tool that was thought to be limited to simple cases and expands its reach to cover the most intricate scenarios. By combining the global view of a universal tree with the detailed memory instructions of a Zielonka tree, the researchers have unlocked a new level of efficiency. This allows for the direct solution of games that were previously too difficult to handle without heavy computational overhead. The findings offer a clearer, faster, and more memory-efficient way to ensure that the systems we rely on can withstand any challenge the environment throws at them.

Technical Summary: Solving Streett and Emerson-Lei Games with Universal Trees

Problem Statement

The paper addresses the computational complexity of solving infinite-duration two-player games with $\omega$ -regular winning conditions, specifically Streett and Emerson-Lei (EL) games. While parity games have recently been shown to be solvable in quasi-polynomial time via the introduction of universal trees, extending these results to more expressive conditions has remained challenging.

Existing approaches for Streett and EL games typically rely on reductions to parity games. However, these reductions often incur significant overheads:

Complexity Blowup: Converting EL conditions to parity games often involves factorial blowups in the number of priorities (e.g., using the Latest Appearance Record construction), leading to time complexities like $O(m \cdot (c!)^2 \cdot n^{1+o(1)})$ .
Memory Inefficiency: Strategies extracted from parity game reductions often embed the memory requirements of both players into the arena, resulting in strategies that are not memory-optimal for the original game.
Limited Direct Understanding: The role of universal trees in direct solutions for non-positional games (where winning strategies require memory) has been unclear. Streett and EL games are known to require memory, analyzed via Zielonka trees, but it was previously unknown if universal trees could be directly applied to solve them without reduction.

Methodology

The authors propose a direct solution framework that integrates universal trees (for bounding progress) with Zielonka trees (for managing memory requirements). The methodology consists of three main components:

1. Hierarchical Trees and Signatures

The paper establishes that winning regions in Streett and EL games can be encoded using mappings into hierarchical trees (a specific structural property of universal trees).

Streett Games: The winning region is partitioned based on the Zielonka-McNaughton algorithm. The authors define "signatures" that map vertices to leaves or subtrees of a universal tree $U(n, k)$ , where $k$ is the number of Streett pairs. These signatures respect the order of attractor computations and recursive sub-problems.
Emerson-Lei Games: The approach is extended using the Zielonka tree $Z(\alpha)$ of the winning condition. Signatures map vertices to pairs consisting of a node in a universal tree $U(n, c/2)$ and a node in the Zielonka tree (or a specific even branching direction). This structure captures the interleaving of memory states required to satisfy complex Boolean combinations of fairness conditions.

2. Rank-Lifting Algorithms (Asymmetric, Enumerative)

The authors define rankings (Streett rankings and EL rankings) over the product of the game vertices, memory states (permutations for Streett; odd-direction sequences for EL), and the universal tree.

Progress Measure: A "good" ranking ensures that Player 0 can always make progress (strictly decreasing the rank) towards satisfying the winning condition, while Player 1 cannot prevent this progress.
Memory Updates: The ranking incorporates memory updates. For Streett games, visiting a "granting" set $G_i$ updates the permutation of pairs. For EL games, visiting specific colors updates the path in the Zielonka tree (odd/even directions).
Algorithm: A rank-lifting algorithm iteratively updates these rankings until a fixpoint is reached. The algorithm starts with minimal ranks and lifts them based on the controllable predecessors and the progress relation defined by the tree structure.
Key Innovation: By using quasi-polynomial universal trees $U(n, k)$ instead of exponentially large ones, the algorithm avoids the exponential dependence on the number of pairs/colors in the ranking domain size.

3. Symbolic Solution (Symmetric, Attractor-Based)

For EL games, the authors also present a symbolic algorithm that bounds the recursion tree of the Zielonka-McNaughton algorithm.

Instead of exploring the full recursion tree of size proportional to the factorial of the number of colors, the algorithm uses universal trees to bound the depth and branching of the recursion.
This approach computes winning regions (without explicitly extracting strategies) by maintaining sets of vertices (dominions) and using hierarchical trees to track the size of these dominions relative to the Zielonka tree structure.

Key Contributions

Direct Solution for Streett Games:
- Introduced Streett rankings based on universal trees.
- Proved that a good Streett ranking exists over $U(n, k)$ for any winning vertex.
- Developed a rank-lifting algorithm solving Streett games with $n$ vertices, $m$ edges, and $k$ pairs in time $O(m \cdot k \log(k) \cdot k! \cdot |U(n, k)|)$ .
- This improves upon the previous best bound of $O(m \cdot k! \cdot (nk!)^{1+o(1)})$ derived from parity reductions.
Direct Solution for Emerson-Lei Games:
- Introduced EL rankings that combine universal trees with Zielonka trees to handle memory requirements.
- Developed a rank-lifting algorithm solving EL games with $n$ vertices, $m$ edges, and $c$ colors in time $O(m \cdot c \log(c) \cdot c! \cdot |U(n, c/2)|)$ .
- This improves upon the previous best bound of $O(m \cdot c! \cdot (nc!)^{1+o(1)})$ .
- Memory Optimality: Unlike reductions to parity games, the strategies extracted from these rankings use memory size at most $m^+_\alpha$ (the optimal memory required for the condition), rather than the potentially larger memory required by the parity reduction.
Symbolic Algorithm for EL Games:
- Presented a symbolic algorithm that bounds the recursion of the Zielonka-McNaughton algorithm using universal trees.
- Achieves a time complexity of $O(m \cdot c \cdot c! \cdot n^{2 \log(c/2)+O(1)})$ , improving over existing symbolic approaches by replacing the factor $n^c$ in the time complexity with $|U(n, c)|$ .
Theoretical Unification:
- Demonstrated that hierarchical trees (a strict form of universal trees) are sufficient to capture the structure of winning regions in non-positional games.
- Showed that standard quasi-polynomial universal trees (e.g., those by Jurdziński and Lazic) are hierarchical, thereby enabling the quasi-polynomial speedup for Streett and EL games.

Results and Complexity Analysis

The paper provides the following complexity improvements (where $|U(n, k)| \approx n^{\log k}$ ):

Streett Games:
- Previous: $O(m \cdot k! \cdot (nk!)^{1+o(1)})$
- New: $O(m \cdot k \log(k) \cdot k! \cdot n^{\log k})$
- Improvement: Removes the quadratic factorial dependence on $k$ in the exponent of $n$ .
Emerson-Lei Games:
- Previous: $O(m \cdot c! \cdot (nc!)^{1+o(1)})$
- New: $O(m \cdot c \log(c) \cdot c! \cdot n^{\log(c/2)})$ (for rank-lifting) and $O(m \cdot c \cdot c! \cdot n^{2 \log(c/2)+O(1)})$ (for symbolic).
- Improvement: Similarly removes the quadratic factorial dependence on $c$ in the exponent of $n$ for the rank-lifting approach, and replaces the $n^c$ factor in symbolic approaches with $|U(n, c)|$ .
Memory: The extracted strategies are memory-optimal, using at most $m^+_\alpha$ memory states, whereas parity reductions often require memory proportional to the size of the reduced parity game (which can be exponential in the original parameters).

Significance and Claims

The paper claims to refute the common view that universal trees are only relevant for games with memoryless (positional) winning strategies. By successfully combining universal trees (for progress measurement) with Zielonka trees (for memory management), the authors lift the quasi-polynomial breakthrough from parity and Rabin games to the more general and complex settings of Streett and Emerson-Lei games.

The significance lies in:

Breaking the "Quadratic Factorial" Barrier: The algorithms break the $(k!)^2$ or $(c!)^2$ dependence on the number of pairs/colors found in previous reduction-based approaches.
Directness: The solutions are direct, avoiding the intermediate step of converting to parity games, which preserves the succinctness of the original winning conditions.
Optimality: The approach yields strategies with optimal memory usage, a property often lost in reduction-based methods.
Conceptual Insight: The work provides a precise recipe (via Zielonka trees) for how rankings for complex conditions are composed by interleaving rankings of simpler, memory-free conditions.

The authors note that their results are consistent with the Exponential Time Hypothesis lower bounds for EL games, as the size of the universal tree remains polylogarithmic in $n$ . They also mention that the approach applies to Muller games, though exact bounds for general Muller conditions are left as future work.