💻 computer science

The memory of $\omega$ -regular and BC( $\Sigma_2^0$ ) objectives

This paper establishes that the memory required for $\omega$ -regular objectives can be computed in NP and coincides for finite and infinite games, while also proving that the memory of the union of two BC( $\Sigma_2^0$ ) objectives is bounded by the product of their individual memories, with these results extending to chromatic memory.

Original authors: Antonio Casares, Pierre Ohlmann

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Antonio Casares, Pierre Ohlmann

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 playing a never-ending board game against a friend. The board is a map with paths, and every time you move, you pick up a colored token. The goal of the game is to collect an infinite sequence of colors that matches a specific "recipe" (the objective). You (Eve) want to follow the recipe; your friend (Adam) wants to stop you.

To win, you need a strategy: a set of rules telling you which path to take next. Sometimes, you can win by just looking at where you are right now (a "memoryless" strategy). But often, you need to remember what happened in the past. Maybe you need to remember "I saw a red token three steps ago, so now I must take the blue path."

The memory of a game objective is simply the smallest number of "mental slots" (or sticky notes) you need to keep in your head to guarantee a win, no matter how tricky the board is.

This paper, written by Antonio Casares and Pierre Ohlmann, solves three major mysteries about how much memory is needed to win these infinite games.

1. The "Finite vs. Infinite" Mystery

The Question: Does it matter if the game board is small (finite) or huge/infinite?
The Old Belief: For a long time, researchers weren't sure if a strategy that works on a small board would also work on a giant, infinite one. Some objectives (like keeping a score from dropping too low) behave differently depending on the board size.
The Paper's Discovery: For a huge class of objectives (called $\omega$ -regular and BC( $\Sigma^0_2$ )), the answer is no, it doesn't matter.

The Analogy: Imagine you are learning to ride a bike. If you can balance on a small, flat driveway, you can also balance on an infinite highway. The paper proves that for these specific types of games, if you can win on a small board with 5 sticky notes, you can win on an infinite board with the same 5 sticky notes.
The Result: They proved that the "memory cost" is the same whether the game is finite or infinite.

2. The "Memory Calculator" Mystery

The Question: Can we actually calculate the exact number of sticky notes needed for a game?
The Old Belief: For decades, nobody knew if there was a computer program that could look at a game's rules and tell you the exact memory required. It was an open question: "Is this even computable?"
The Paper's Discovery: Yes, we can calculate it!

The Analogy: Before this, trying to find the memory limit was like trying to find a specific grain of sand on a beach without a map. The authors built a new "map" (a specific type of machine called an automaton).
The Result: They created a method to check if a game needs 1, 2, or 100 sticky notes. They showed that a computer can solve this problem relatively quickly (in a complexity class called NP). This is the first time this has been proven for such a broad range of games.

3. The "Team-Up" Mystery (Kopczyński's Conjecture)

The Question: If you combine two games into one big game, how much memory do you need?
The Scenario: Imagine Game A needs 2 sticky notes to win, and Game B needs 3. If you play a game where you win if you satisfy either Game A or Game B, do you need 2 + 3 = 5 notes? Or maybe 2 $\times$ 3 = 6?
The Paper's Discovery: If you combine two objectives, the memory needed is at most the product of their individual memories.

The Analogy: Think of it like packing for a trip. If you need 2 suitcases for your clothes and 3 for your electronics, and you are allowed to take either the clothes trip or the electronics trip, you don't need 5 suitcases. You need a way to organize them. The paper proves that the "storage space" needed for the combined game is roughly the multiplication of the two spaces (2 $\times$ 3 = 6), not the sum.
The Catch: This works perfectly if one of the games is "prefix-independent" (meaning it doesn't matter what you did at the very start; only the future matters).

The Secret Weapon: "Universal Graphs"

How did they solve this? They used a tool called Universal Graphs.

The Analogy: Imagine you want to test if a new car is fast enough for any race track. Instead of building every possible track, you build one "Super Track" that contains every possible turn and straightaway found in any real track. If your car can handle the Super Track, it can handle any track.
The Paper's Innovation: They built these "Super Tracks" (Universal Graphs) specifically for memory. They showed that if you can build a Super Track with a certain structure (called $\varepsilon$ -completable), then the game has low memory. This allowed them to turn a hard game-theory problem into a machine-checking problem.

Summary

In plain English, this paper says:

Consistency: For many complex games, the memory needed to win is the same whether the game is small or infinite.
Solvability: We can now write a computer program to calculate exactly how much memory is needed to win these games.
Combination: When you mix two games, the memory needed grows predictably (multiplicatively), not chaotically.

This work is a big step forward for computer science, helping us understand the complexity of automated systems, verification, and synthesis without needing to simulate every possible scenario.

Technical Summary: The Memory of $\omega$ -Regular and $BC(\Sigma^0_2)$ Objectives

Problem Statement
In the context of 2-player zero-sum infinite duration games on (potentially infinite) graphs, the memory of an objective $W$ is defined as the smallest integer $k$ such that, in any game where Eve has a winning strategy, she possesses a winning strategy implementable by a finite automaton with at most $k$ memory states. While the decidability of positionality (memory $k=1$ ) for $\omega$ -regular objectives was recently established, the general problem of deciding the memory of $\omega$ -regular objectives remained open. Specifically, it was unknown whether computing the memory was decidable, nor was it known if the memory required over finite game graphs coincided with that over arbitrary infinite graphs. Furthermore, the behavior of memory under the union of objectives (Generalised Kopczyński's conjecture) was an open question for objectives requiring memory.

Methodology
The authors introduce a novel characterisation of objectives with memory $\le k$ based on $k$ -wise $\varepsilon$ -completable automata. This approach extends the concept of universal graphs and $\varepsilon$ -completable automata, previously used for positionality, to the setting of finite memory.

$k$ -wise $\varepsilon$ -completable Automata: An automaton is $k$ -wise $\varepsilon$ -complete if its states (partitioned into $k$ memory chains) can be augmented with $\varepsilon$ -transitions to form a structure where, for every even priority $x$ and memory state $m$ , the states with memory $m$ are totally preordered. Specifically, for any pair of states $(q, m)$ and $(q', m)$ , either there is an $\varepsilon$ -transition from $q$ to $q'$ with priority $x$ , or a transition from $q'$ to $q$ with priority $x+1$ .
Extraction Lemmas: The core technical innovation involves extracting homogeneous substructures from infinite or large finite graphs.
- For the infinitary case (Section 3.1), the authors use a combinatorial lemma (Lemma 12) to extract "everywhere cofinal" trees from the universal graph $S_\kappa^d$ (where $\kappa = 2^{\aleph_0}$ ), ensuring that domination relations between states are uniform across levels.
- For the finitary case (Section 3.2), they adapt these extraction techniques to finite automata, utilizing "regular words" and synchronised subwords (Lemma 24) to handle finite branching and ensure the existence of a $k$ -blowup that is $\varepsilon$ -completable.
Cascade Products: The proofs rely heavily on the cascade product of a deterministic automaton with a universal graph (or signature tree) to encode all possible accepting behaviors, followed by the construction of a $k$ -blowup that preserves the language while satisfying the $\varepsilon$ -completeness condition.

Key Contributions and Results

Characterisation Theorem (Theorem 7): The paper establishes a necessary and sufficient condition for a $BC(\Sigma^0_2)$ objective (recognised by a potentially infinite deterministic parity automaton) to have memory $\le k$ . The following are equivalent:
- The objective has memory $\le k$ on games of size $\le 2^{2^{\aleph_0}}$ .
- Every automaton recognising the objective admits a $k$ -blowup that is $k$ -wise $\varepsilon$ -complete.
- There exists a deterministic $k$ -automaton that is $k$ -wise $\varepsilon$ -completable and recognises the objective.
- For every cardinal $\kappa$ , there exists a $(\kappa, W)$ -universal graph that is well-founded and $k$ -wise $\varepsilon$ -complete.
- The objective has memory $\le k$ on arbitrary games.
Decidability in NP (Corollary 9): For $\omega$ -regular objectives (finite automata), the memory (and chromatic memory) can be computed in NP. The algorithm guesses a candidate memory size $k$ , a deterministic automaton of size $\le kn$ , and an $\varepsilon$ -completion, then verifies language inclusion in polynomial time. Prior to this work, the decidability of memory for open $\omega$ -regular objectives was unknown.
Finite-to-Infinite Lift (Corollary 8): The paper proves that for $\omega$ -regular objectives, the memory required over finite game graphs is identical to that required over arbitrary (infinite) game graphs. This resolves a conjecture by Vandenhove for the $\omega$ -regular case.
Closure Under Union (Theorem 10): The authors prove a strong form of the Generalised Kopczyński's conjecture for $BC(\Sigma^0_2)$ objectives. If $W_1$ and $W_2$ are objectives with memories $k_1$ and $k_2$ respectively, and $W_2$ is prefix-increasing, then the memory of $W_1 \cup W_2$ is at most $k_1 \cdot k_2$ . The bound is shown to be tight.
Chromatic Memory: All results apply equally to chromatic memory, where strategies can only update their memory state based on the colour of the edge seen, rather than the edge itself.

Significance and Claims
The paper claims to provide the first known characterisation of (chromatic) memory for $\omega$ -regular objectives, moving beyond the previously restricted classes (like Muller or closed objectives). By establishing that memory computation is in NP, it shifts the problem from an open decidability question to a tractable complexity class. The authors emphasize that their proof techniques, which involve extracting structures from infinite graphs and manipulating ordinal numbers, are distinct from previous work on positionality (which relied on successive automata transformations) and are notably shorter.

The results extend the scope of memory analysis to the broader class of $BC(\Sigma^0_2)$ languages, which includes non- $\omega$ -regular objectives such as energy and mean-payoff games, as well as languages recognised by deterministic $\omega$ -Turing machines. The paper explicitly notes that while it recovers the finite-to-infinite lift for $\omega$ -regular objectives, it does not recover the "1-to-2-player lift" (asymmetric lift) for memory $k > 1$ , as counterexamples exist.

Limitations and Open Questions
The authors acknowledge that while they establish decidability in NP, the exact complexity (specifically whether it is in P) remains open. They also note that their methods currently do not extend to the class $\Delta^0_3$ due to difficulties in generalising the extraction lemma. The question of whether an asymmetric lift exists for chromatic memory in $\omega$ -regular objectives remains open.