<figure><img src="image_1.png" /></figure>

HAL
open science

# Characterising memory in infinite games

Antonio Casares, Pierre Ohlmann

► To cite this version:

Antonio Casares, Pierre Ohlmann. Characterising memory in infinite games. Logical Methods in Computer Science, 2025, Volume21,Issue1, 10.46298/lmcs-21(1:28)2025 . hal-05376840

HAL Id: hal-05376840

https://hal.science/hal-05376840v1

Submitted on 21 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# CHARACTERISING MEMORY IN INFINITE GAMES

ANTONIO CASARES ◦ª AND PIERRE OHLMANN ◦ᵇ

ª University of Warsaw, Poland
*e-mail address:* antoniocasares@mimuw.edu.pl

ᵇ CNRS, Laboratoire d'Informatique et des Systèmes, Marseille, France
*e-mail address:* pierre.ohlmann@lis-lab.fr

**ABSTRACT.** This paper is concerned with games of infinite duration played over potentially infinite graphs. Recently, Ohlmann (TheoretiCS 2023) presented a characterisation of objectives admitting optimal positional strategies, by means of universal graphs: an objective is positional if and only if it admits well-ordered monotone universal graphs. We extend Ohlmann's characterisation to encompass (finite or infinite) memory upper bounds.

We prove that objectives admitting optimal strategies with $\varepsilon$-memory less than $m$ (a memory that cannot be updated when reading an $\varepsilon$-edge) are exactly those which admit well-founded monotone universal graphs whose antichains have size bounded by $m$. We also give a characterisation of chromatic memory by means of appropriate universal structures. Our results apply to finite as well as infinite memory bounds (for instance, to objectives with finite but unbounded memory, or with countable memory strategies).

We illustrate the applicability of our framework by carrying out a few case studies, we provide examples witnessing limitations of our approach, and we discuss general closure properties which follow from our results.

This document contains hyperlinks. Each occurrence of a notion is linked to its definition. On an electronic device, the reader can click on words or symbols (or just hover over them on some PDF readers) to see their definition.

## 1. INTRODUCTION

1.1. **Context.** We study zero-sum turn-based games on graphs, in which two players, that we call Eve and Adam, take turns in moving a token along the edges of a given (potentially infinite) edge-coloured directed graph. Vertices of the graph are partitioned into those belonging to Eve and those belonging to Adam. When the token lands in a vertex owned by player X, it is this player who chooses where to move next. This interaction, which is sometimes called a play, goes on in a non-terminating mode, producing an infinite sequence of colours. We fix in advance an objective *W*, which is a language of infinite sequences of

*Key words and phrases:* Infinite duration games; Memory; Universal graphs.

This paper is an extended version of [CO23], including full proofs and additional examples.

Antonio Casares is supported by the Polish National Science Centre (NCN) grant "Polynomial finite state computation" (2022/46/A/ST6/00072).

<figure><img src="image_3.png" /></figure>
colours; plays producing a sequence of colours in W are considered to be winning for Eve, and plays that do not satisfy the objective W are winning for the opponent Adam.

In order to achieve their goal, players use strategies, which are representations of the course of all possible plays together with instructions on how to act in each scenario. In this work, we are interested in optimal strategies for Eve, that is, strategies that guarantee a victory whenever this is possible. More precisely, we are interested in the complexity of such strategies, or in other words, in the succinctness of the representation of the space of plays. The simplest strategies are those that assign in advance an outgoing edge to each vertex owned by Eve, and always play along this edge, disregarding all the other features of the play. All the information required to implement such a strategy appears in the game graph itself. These strategies are called positional (or memoryless). However, in some scenarios, playing optimally requires distinguishing different plays that end in the same vertex; one should remember other features of plays. An example of such a game is given in Figure 1.

<figure><img src="image_4.png" /><figcaption>Figure 1: On the left, a game with objective $W = (ab)^\omega$; in words, Eve should ensure that the play alternates between a-edges and b-edges. We represent Eve's vertices as circles and Adam's as squares. On the right, a winning strategy for Eve which uses one state of memory for $v_0$, one state of memory for $v_1$, and two states of memory for $v_2$. Note that two states of memory for $v_2$ are required here: a positional strategy would always follow the same self-loop and therefore cannot win. One can prove that any game with objective $W$ which is won by Eve can be won even when restricting to strategies with two states of memory, such as the one above. To conclude, the memory requirements for $W$ is exactly two.</figcaption></figure>

Given an objective $W$, the question we are interested in is:

> "What is the minimal strategy complexity required for Eve to play optimally in all games with objective $W$?"

**Positional objectives and universal graphs.** As mentioned above, an important special case is that of positional objectives, those for which Eve does not require any memory to play optimally. A considerable body of research, with both theoretical and practical reach, has been devoted to the study of positionality. By now it is quite well-understood which objectives are positional for both players (bi-positional), thanks to the works of Gimbert and Zielonka [GZ05] for finite game graphs, and of Colcombet and Niwiński [CN06] for arbitrary game graphs. However, a precise understanding of which objectives are positional for Eve – regardless of the opponent – remains somewhat elusive, even though this is a more relevant question in most application scenarios.
A recent progress in this direction was achieved by Ohlmann [Ohl23], using totally ordered monotone universal graphs. Informally, an edge-coloured graph is universal with respect to a given objective W if it satisfies W (all paths satisfy W), and homomorphically embeds all graphs satisfying W. An ordered graph is monotone if its edge relations are monotone:

$$v \ge u \stackrel{c}{\to} u' \ge v' \implies v \stackrel{c}{\to} v', \text{ for every colour } c.$$

Ohlmann's main result is a characterisation of positionality (assuming existence of a neutral letter): an objective is positional if and only if it admits well-ordered monotone universal graphs.

**From positionality to finite memory.** Positional objectives have good theoretical properties and do often arise in applications (in particular, parity, Rabin or energy objectives). It is also true, however, that this class lacks in expressivity and robustness: only a handful of objectives are positional, and very few closure properties are known to hold for positional objectives<fnref n="1" />.

In contrast, objectives admitting optimal finite memory strategies are much more general; for instance they encompass all $\omega$-regular objectives [GH82] (in fact, it was recently established [BRV23] that optimal finite chromatic memory for both players characterises $\omega$-regularity). Moreover, in practice, finite memory strategies can be implemented by means of a program, and memory bounds for Eve directly translates in space and time required to implement controllers, which gives additional motivation for their systematic study.

Formally, when moving from positionality to finite memory, a few modelling difficulties arise, giving rise to a few different notions. Most prominently, one may or may not include uncoloured edges ($\varepsilon$-edges) in the game, over which the memory state cannot be updated; additionally one may or may not restrict to chromatic memories, meaning those that record only the colours that have appeared so far. We now discuss some implications of these two choices.

It is known that allowing $\varepsilon$-edges impacts the difficulty of the games, in the sense that it may increase the memory required for winning strategies [Cas22, Kop08, Zie98], thus leading to two different notions of memory (that we call $\varepsilon$-memory and $\varepsilon$-free memory). It is natural to wonder whether one of the two notions should be preferred over the other. We argue that allowing $\varepsilon$-edges turns out to be more natural in many applications. First, we notice that currently existing characterisations of the memory (for Muller objectives [DJW97] and for topologically closed objectives [CFH14]) do only apply to the case of $\varepsilon$-memory. More importantly, games induced by logical formulas in which players are interpreted as the existential player (controlling existential quantifiers and disjunctions) and the universal player (controlling universal quantifiers and conjunctions) naturally contain $\varepsilon$-edges (along which the memory indeed should not be allowed to be updated).

It was originally conjectured by Kopczyński [Kop08] that chromatic strategies have the same power than non-chromatic ones. It was not until recently that this conjecture was refuted [Cas22], and since then several works have provided new examples separating both notions [CCL22, Koz22b, Koz22c]. It now appears from recent dedicated works [BORV23, BRV23, BRO$^+$22, Cas22] that chromatic memory is an interesting notion in itself.

<footnote n="1">¹Kopczyński conjectured in his thesis [Kop08] that positional prefix-independent objectives are closed under union. This conjecture was recently disproved by Kozachinskiy [Koz22a] over finite game graphs, but it remains open for infinite graphs.</footnote>
The main challenge in the study of strategy complexity is to prove upper bounds on memory requirements of a given objective. A great feature of Ohlmann's result [Ohl23] is that it turns a question about games to a question about graphs, which are easier to handle. Despite its recent introduction, Ohlmann's framework has already proved instrumental for deriving strong positionality results in the context of objectives recognised by finite Büchi automata [BCRV24], and more recently for arbitrary $\omega$-regular objectives [CO24].

**1.2. Contribution.** The present paper builds on the aforementioned work of Ohlmann by extending it to encompass the more general setting of finite (or infinite) memory bounds. This yields the first known characterisation results for objectives with given memory bounds, and provides a (provably) general tool for establishing memory upper bounds.

Doing so requires relaxing from totally to partially ordered graphs, while keeping the same monotonicity requirement, along with some necessary technical adjustments. We essentially prove that the memory of an objective corresponds to the size of antichains in its well-founded monotone universal graph; however it turns out that the precise situation is more intricate. It is summed up in Figure 2 and explained in more details below.

<figure><img src="image_5.png" /><figcaption>Figure 2: A summary of our main contributions. The three larger boxes correspond to the three regimes encompassed by our results: finite memory, locally finite memory and larger cardinal bounds. Each of the smaller boxes correspond to classes of objectives, where “struct.” stands for “existence of well-founded monotone universal graphs”; for example, the box labelled “$\varepsilon$-separated struct. breadth $\le m$” stands for “existence of $\varepsilon$-separated well-founded monotone universal graphs of breadth $\le m$”. The dotted implications follow from combining other implications in the figure. For $m = 1$, all notions collapse to a single equivalence, which corresponds to Ohlmann’s characterisation.</figcaption></figure>

It is convenient for us to define strategies directly as graphs (see Figure 1 for an example, and Section 2 for formal details), which allows us in particular to introduce new classes of objectives such as those admitting locally finite memory, discussed in more details below. For the well-studied case of finite memory bounds, our definition of memory coincides with the usual one.
**Universal structures for memory.** Our main contribution lies in introducing generalisations of Ohlmann's structures, and proving general connections between existence of such universal structures for a given objective *W*, and memory bounds for *W* (Section 3.1).

The first variant we propose is obtained by relaxing the monotonicity requirement to partially ordered graphs; Theorem 3.2 states that (potentially infinite) bounds on antichains of a well-founded monotone universal graph translate to memory bounds.

The second variant we propose, called $\varepsilon$-separated structures, is tailored to capture $\varepsilon$-memory. These are monotone graphs where the partial order coincides with $\xrightarrow{\varepsilon}$ and is constrained to be a disjoint union of well-orders; the breadth of such a graph refers to the number of such well-orders. Theorem 3.1 states that the existence of such universal structures of breadth $\mu$ actually characterises having $\varepsilon$-memory $\le \mu$. Additionally, we define chromatic $\varepsilon$-separated structures (over which each colour acts uniformly), and establish that they capture $\varepsilon$-chromatic memory.

Applying (infinite) Dilworth's theorem we obtain that for finite $m$, one may turn any monotone graph of width $m$ to an $\varepsilon$-separated one with breadth $m$ (Proposition 3.5), and therefore in the setting of finite memory, the two notions collapse. We are able to establish most (but not all) of our results in the more general framework of quantitative valuations; similarly as Ohlmann [Ohl23], we show how the notions instantiate in the qualitative case, how they can be simplified assuming prefix-invariance properties, and propose a general useful tool for deriving universality proofs (Lemma 3.8).

**Counterexamples for a complete picture.** We provide additional negative results (Section 5) which set the limits of our approach, completing the picture in Figure 2. Namely, we build two families of counterexamples that are robust to larger cardinals; these give general separations of $\varepsilon$-free memory and $\varepsilon$-memory<fnref n="2" /> (Proposition 5.2), and negate the possibility of a converse for Theorem 3.2 (Proposition 5.1). This supports our informal claim that $\varepsilon$-memory is better behaved than $\varepsilon$-free memory.

**Examples and applications.** We argue (Section 4) that our framework provides a very useful and flexible tool for studying memory requirements given concrete objectives; we provide a few illustrative examples for which we derive upper and lower bounds for each memory type. We also illustrate the applicability of our tool by showing that the two available general characterisations of memory for special classes of objectives, namely, the ones of Colcombet, Fijalkow and Horn [CFH14] for topologically closed objectives, and of Dziembowski, Jurdziński and Walukiewicz [DJW97] for Muller objectives, can both be understood as constructions of monotone universal graphs.

**Closure properties.** Finally, we discuss how our characterisations can be exploited for deriving closure properties on some classes of objectives (Section 6). Apart from Ohlmann's result on lexicographic products of prefix-independent positional objectives [Ohl23], no such closure properties are known. Extending Ohlmann's proof to our framework, we prove that if $W_1$ and $W_2$ are prefix-independent objectives with $\varepsilon$-memory $m_1$ and $m_2$, then their lexicographical product $W_1 \times W_2$ has $\varepsilon$-memory $\le m_1 m_2$. We also discuss a few implications of this result.

We then propose a new class of objectives with good properties, namely, objectives with locally finite memory: for each game, there exists a strategy which uses a finite

<footnote n="2">²This result was already known for finite memory [Cas22].</footnote>
(though possibly unbounded, even when the game is fixed) amount of memory states for each vertex. These objectives are connected with the theory of well-quasi orders (wqo), since they correspond to monotone universal graphs which are well-founded and have finite antichains. We obtain from the fact that wqo's are closed under intersections, that intersections of objectives with finite ε-memory have locally finite memory; an example is given by conjunctions of energy objectives which have unbounded finite memory even though energy objectives are positional. This hints at a general result, which is not implied by our characterisations but we conjecture to be true, that objectives with finite (possibly unbounded) memory are closed under intersection.

We end our paper by providing yet another application of our characterisation, establishing that prefix-independent $\Sigma_2^0$ objectives with finite memory are closed under countable unions. As of today, this is the only known (non-obvious) closure property pertaining to objectives with finite memory.

## 2. PRELIMINARIES

For a finite or infinite word $w \in C^* \cup C^\omega$ we denote by $w_i$ the letter at position $i$ and by $|w|$ its length. For notations concerning order and set theory we refer the reader to Appendix A.

### 2.1. Graphs and morphisms.

**Graphs, paths and trees.** A C-pregraph G, where C is a (potentially infinite) set of colours, is given by a set of vertices $V(G)$, and a set of coloured directed edges $E(G) \subseteq V(G) \times C \times V(G)$. We write $v \xrightarrow{c} v'$ for an edge $(v, c, v')$, say that it is outgoing from v, incoming in v' and has colour c. A C-graph G is a C-pregraph without sinks: from all $v \in V(G)$ there exists an outgoing edge $v \xrightarrow{c} v' \in E(G)$. We often say c-edges to refer to edges with colour c, and sometimes C'-edges for $C' \subseteq C$ for edges with colour in C'.

A path in a pregraph G is a finite or infinite sequence of edges of the form $\pi = (v_0 \xrightarrow{c_0} v_1)(v_1 \xrightarrow{c_1} v_2)\dots$, which for convenience we denote by $\pi = v_0 \xrightarrow{c_0} v_1 \xrightarrow{c_1} \dots$. We say that $\pi$ is a path from $v_0$ in G. By convention, the empty path is a path from $v_0$, for any $v_0 \in V(G)$. If $\pi$ is a finite path, it is of the form $v_0 \xrightarrow{c_0} v_1 \xrightarrow{c_1} \dots \xrightarrow{c_{n-1}} v_n$, and in this case we say that it is a path from $v_0$ to $v_n$ in G. We let $\Pi_{v_0}^\infty(G) \subseteq E(G)^\omega$ and $\Pi_{v_0}^{\text{fin}}(G) \subseteq E(G)^*$ respectively denote the sets of infinite and finite paths from $v_0$ in G.

Given a subset $X \subseteq V(G)$ of vertices of a pregraph G, we let $G|_X$ denote the restriction of G to X, which is the graph given by $V(G|_X) = X$ and $E(G|_X) = E(G) \cap (X \times C \times X)$. Given a vertex $v \in V(G)$, we let $G[v]$ denote the restriction of G to vertices that are reachable from v.

A C-tree (resp. C-pretree) T is a C-graph (resp. C-pregraph) with an identified vertex $t_0 \in V(T)$ called its root, with the property that for each $t \in V(T)$, there is a unique path from $t_0$ to t. Note that since graphs have no sinks, trees are necessarily infinite. We remark that $T[t]$ represents the subtree rooted at t (if T is a tree, $T[t]$ is also a tree with root t).

When it is clear from context, we omit C and simply say “a graph” or “a tree”.

The size of a graph G (and by extension, of a tree) is the cardinality of $V(G)$.
**Morphisms and unfoldings.** A morphism $\phi$ between two graphs $G$ and $H$ is a map $\phi: V(G) \to V(H)$ such that for each edge $v \xrightarrow{c} v' \in E(G)$ it holds that $\phi(v) \xrightarrow{c} \phi(v') \in E(H)$. We write $\phi: G \to H$ in this case, and sometimes say that $H$ embeds $G$. Note that morphisms preserve paths: if $v_0 \xrightarrow{c_0} v_1 \xrightarrow{c_1} \dots$ is a path in $G$, then $\phi(v_0) \xrightarrow{c_0} \phi(v_1) \xrightarrow{c_1} \dots$ is a path in $H$. An isomorphism is a bijective morphism whose inverse is a morphism; two graphs are isomorphic if they are connected by an isomorphism (stated differently, they are the same up to renaming the vertices). The composition of two morphisms is a morphism.

Given a graph $G$ and an initial vertex $v_0 \in G$, the unfolding of $G$ from $v_0$ is the tree $U$ with vertex set $V(U) = \Pi_{v_0}^{\text{fin}}(G)$ and edges

$$E(U) = \{(v_0 \xrightarrow{c_0} \dots \xrightarrow{c_{n-1}} v_n) \xrightarrow{c_n} (v_0 \xrightarrow{c_0} \dots \xrightarrow{c_{n-1}} v_n \xrightarrow{c_n} v_{n+1}) \mid v_n \xrightarrow{c_n} v_{n+1} \in E(G)\}.$$

Note that the map $(v_0 \xrightarrow{c_0} \dots \xrightarrow{c_{n-1}} v_n) \mapsto v_n$ (with the empty path mapped to $v_0$) defines a morphism from $U$ to $G$.

## 2.2. Valuations, games, strategies and memory.

**Valuations and objectives.** A C-valuation is a map $\text{val}: C^\omega \to X$, where $X$ is a complete linear order (that is, a total order in which all subsets have both a supremum and an infimum). The value $\text{val}_G(v_0)$ of a vertex $v_0 \in V(G)$ in a graph $G$ is the supremum value of infinite paths from $v$, where the value of an infinite path $\pi = v_0 \xrightarrow{c_0} v_1 \xrightarrow{c_1} \dots$ is defined to be $\text{val}(\pi) = \text{val}(c_0c_1\dots)$.

In the important special case where $X = \{\perp, \top\}$, $\perp < \top$, we identify<fnref n="3" /> $\text{val}$ with $W = \text{val}^{-1}(\perp) \subseteq C^\omega$, and say that $\text{val}$ (or $W$) is an *objective*. In a graph $G$, a path with value $\perp$ (equivalently, whose sequence of colours belongs to $W$) is said to *satisfy* $W$, and a vertex $v_0$ with value $\perp$ (equivalently, all paths from $v_0$ satisfy $W$) is also said to satisfy $W$. A graph is said to satisfy $W$ if all its vertices satisfy it.

**Games.** A C-game is a tuple $G = (G, V_{\text{Eve}}, v_0, \text{val})$, where $G$ is a C-graph, $V_{\text{Eve}}$ is a subset of $V(G)$, $v_0 \in V(G)$ is an identified initial vertex, and $\text{val}: C^\omega \to X$ is a C-valuation. We interpret $V_{\text{Eve}}$ to be the set of vertices controlled by the first player, *Eve*, and we will write $V_{\text{Adam}} = V(G) \setminus V_{\text{Eve}}$ for the vertices controlled by her opponent, *Adam*. A game is played as follows: starting from $v_0$, successive moves are played where the player controlling the current vertex $v$ chooses an outgoing edge $v \xrightarrow{c} v'$ and proceed to $v'$. This interaction goes on forever, producing and infinite path $\pi$ from $v_0$. Eve's goal is to minimise the value of the produced path $\pi$, whereas Adam aims to maximise it.

In this paper, we are interested in questions of strategy complexity for Eve: if she wins, how much memory is required/sufficient? Formally, these are independent of questions of determinacy (is there a winner?). As a result, we will only ever consider strategies for Eve.

<footnote n="3">³When considering an objective as a set of infinite words rather than a valuation $C^\omega \to \{\perp, \top\}$, we lose the information that $C$ is the set of colours that we are considering. This may be important in some cases, for instance $\emptyset \subseteq \{0\}^\omega$ and $\emptyset \subseteq \{1, 2\}^\omega$ are not the same objective. However, it will always be clear from context what the set of colours is, and therefore, by a slight abuse, we avoid the hassle of defining objectives as tuples $(W, C)$.</footnote>
**Strategies.** A strategy in the game $\mathcal{G}$ is a tuple $\mathcal{S} = (S, \pi_{\mathcal{S}}, s_0)$ where $S$ is a graph, $\pi_{\mathcal{S}}$ is a morphism $\pi_{\mathcal{S}}: S \to G$ called the $\mathcal{S}$-projection and $s_0 \in V(S)$ satisfying:

* $\pi_{\mathcal{S}}(s_0) = v_0$,

* for all $v \in V_{\text{Adam}}$, all outgoing edges $v \xrightarrow{c} v' \in E(G)$ and all $s \in \pi_{\mathcal{S}}^{-1}(v)$, there is $s' \in \pi^{-1}(v')$ such that $s \xrightarrow{c} s' \in E(S)$ (see Figure 3).

Note that the requirements that $S$ is a graph and $\pi_{\mathcal{S}}$ a morphism impose that for all $v \in V_{\text{Eve}}$ and $s \in \pi_{\mathcal{S}}^{-1}(v)$, $s$ has an outgoing edge $s \xrightarrow{c} s' \in E(S)$ satisfying $\pi_{\mathcal{S}}(s) = v \xrightarrow{c} \pi_{\mathcal{S}}(s') \in E(G)$.

<figure><img src="image_6.png" /><figcaption>Figure 3: Diagram illustrating the definition of a strategy. We use squares to represent vertices controlled by Adam and circles for vertices controlled by Eve. In this figure, it does not matter who controls $v'$.</figcaption></figure>

We remark that we do not impose that for each $v \in V_{\text{Eve}}$ and $s \in \pi_{\mathcal{S}}^{-1}(v)$, $s$ has *exactly one* outgoing edge. Stated differently, non-determinism is allowed in this definition of strategy. As the upcoming definition of value of a strategy will clarify, we can interpret that Adam decides how to resolve this non-determinism.

On an informal level, a strategy $\mathcal{S} = (S, \pi_{\mathcal{S}}, s_0)$ from $v_0 \in G$ is used by Eve to play in the game $\mathcal{G}$ as follows:

* whenever the game is in a position $v \in V(G)$, the strategy is in a position $s \in \pi_{\mathcal{S}}^{-1}(v)$;

* initially, the position in the game is $v_0$, and the position in the strategy is $s_0 \in \pi_{\mathcal{S}}^{-1}(v_0)$;

* if the position $v$ in the game belongs to $V_{\text{Adam}}$, and Adam chooses the edge $v \xrightarrow{c} v'$ in $G$, then the strategy state is updated following an edge $s \xrightarrow{c} s'$ in $S$ with $\pi_{\mathcal{S}}(s') = v'$, which exists by definition of $\mathcal{S}$ (if multiple options exist, Adam chooses one);

* if the position $v$ in the game belong to $V_{\text{Eve}}$, then the strategy specifies at least one successor $s \xrightarrow{c} s'$ from the current $s \in \pi^{-1}(v)$, and the game proceeds along the edge $v \xrightarrow{c} \pi(s')$ (if multiple options exist in the strategy, which corresponds to the non-determinism mentioned above, then Adam chooses one).

Note that infinite sequences of colours produced when playing as above are exactly labels of infinite paths from $s_0$ in $S$.

The *value* $\text{val}(\mathcal{S})$ of a strategy $\mathcal{S}$ is $\text{val}_S(s_0)$. The *value* $\text{val}(\mathcal{G})$ of a game is the infimum value among its strategies. If $\text{val}$ is an objective, we say that $\mathcal{S}$ is *winning* if $\text{val}_S(s_0) = \perp$, and we say that *Eve wins* a game $\mathcal{G}$ if $\text{val}(\mathcal{G}) = \perp$.

The following observation is standard (in fact, it is usually taken as the definition of a strategy).

**Lemma 2.1.** *The value of a game is reached with strategies that are trees.*
**Proof.** Let $\mathcal{G}$ be a game and $\mathcal{S} = (S, \pi_S, s_0)$ a strategy over $\mathcal{G}$. Consider the unfolding $U$ of $S$ from $s_0$, with morphism $\phi: U \to S$. It is a direct check that $\mathcal{U} = (U, \pi_{\mathcal{U}}, \epsilon)$, where $\epsilon$ is the root of $U$ (represented by the empty path), and $\pi_{\mathcal{U}} = \pi_S \circ \phi: U \to G$ is a strategy. Moreover, the fact that $\phi: U \to S$ is a morphism mapping $\epsilon$ to $s_0$ immediately yields $\mathrm{val}(\mathcal{U}) \le \mathrm{val}(\mathcal{S})$. $\square$

**Memory.** For a strategy $\mathcal{S} = (S, \pi_S, s_0)$, we interpret the fibres $\pi_S^{-1}(v)$ as memory spaces. Given a cardinal $\mu$, we say that $\mathcal{S}$ has *memory* strictly less than $\mu$, (resp. less than $\mu$) if for all $v \in V(G)$, $|\pi_S^{-1}(v)| < \mu$ (resp. $|\pi_S^{-1}(v)| \le \mu$). As it will appear later on, it is convenient for us to be able to use both strict and non-strict inequalities. By means of clarity and conciseness, we usually simply write "$\mathcal{S}$ has memory < $\mu$" (resp. $\le \mu$) instead of "$\mathcal{S}$ has memory strictly less than $\mu$ (resp. less than $\mu$)$".

We say that a valuation val has *memory strictly less than* $\mu$, or $< \mu$, (resp. less than $\mu$, or $\le \mu$) if in all games with valuation val, the value is reached with strategies with memory $< \mu$.

Conversely, we say that val has *memory at least* $\mu$ (resp. strictly more than $\mu$), or $\ge \mu$ (resp. $> \mu$), if it does not have memory $< \mu$ (resp. $\le \mu$): there exists a game with valuation val in which Eve cannot reach the value with strategies with memory $< \mu$ (resp. $\le \mu$).

Finally, if there exists$^4 \mu$ such that val has memory $\ge \mu$, but memory $< \alpha$ for all $\alpha > \mu$, then we say that val has *memory exactly* $\mu$.

We say that val is *positional$^5$* if it has memory $\le 1$.

**Product strategies, chromatic strategies.** A strategy $\mathcal{S} = (S, \pi_S, s_0)$ in the game $\mathcal{G}$ is a *product strategy* over a set $M$ if $V(S) \subseteq V(G) \times M$, with $\pi_S(v, m) = v$. We call the elements of $M$ *memory states*. Note that the memory in a product strategy over $M$ is $\le |M|$, since fibers are included in $M$. A product strategy is *chromatic* if there is a map $\delta: M \times C \to M$ such that for all $(v, m) \xrightarrow{c} (v', m') \in E(S)$ we have $m' = \delta(m, c)$. We say in this case that $\delta$ is the *update function* of $\mathcal{S}$. In words, the update of the memory state in a chromatic strategy depends only on the current memory state and the colour that is read. A valuation val has *chromatic memory* $< \mu$ (resp. $\le \mu$) if in all games with valuation val, the value is reached with chromatic strategies with memory $< \mu$ (resp. $\le \mu$).

**$\varepsilon$-games and $\varepsilon$-strategies.** Fix a set of colours $C$, a fresh colour $\varepsilon \notin C$, and let $C^\varepsilon = C \sqcup \{\varepsilon\}$. The $C$-projection of an infinite sequence $w \in (C^\varepsilon)^\omega$ is the (finite or infinite) sequence $w_C \in C^* \cup C^\omega$ obtained by removing all $\varepsilon$'s in $w$. Given a $C$-valuation val : $C^\omega \to X$, define its $\varepsilon$-extension val$^\varepsilon$ to be given by

$$ \mathrm{val}^{\varepsilon}(w) = \begin{cases} \mathrm{val}(w_C), & \text{if } |w_C| = \infty, \\ \inf_{w' \in C^\omega} \mathrm{val}(w_C w'), & \text{otherwise.} \end{cases} $$

It is the unique extension of val with $\varepsilon$ as a strongly neutral colour, in the sense of Ohlmann [Ohl23]. In particular, if $W$ is an objective and $w \in C^*$, $w\varepsilon^\omega \in W^\varepsilon$ unless $w$ has no winning continuation in $W$.

<footnote>$^4$It might be that there is no cardinal $\mu$ such that val has memory exactly $\mu$ (intersections of energy objectives are an example, see Section 6.2).</footnote>

<footnote>$^5$This is sometimes called *half-positionality* in the literature.</footnote>
An ε-game $\mathcal{G}$ is a $C^\epsilon$-game with valuation val$^\epsilon$. An ε-strategy over such a game is a product strategy $S = (S, \pi_S, s_0)$ over some set $M$ such that $(v, m) \xrightarrow{\epsilon} (v', m') \in E(S)$ implies $m = m'$. Intuitively, Eve is not allowed to update the state of the memory when an ε-edge is traversed. The memory of an ε-strategy is defined to be $|M|$. A valuation val has ε-memory $< \mu$ (resp. $\leq \mu$) if in all ε-games with valuation val$^\epsilon$, the value is attained by ε-strategies with memory $< \mu$ (resp. $\leq \mu$). Having ε-memory $\geq \mu$, $> \mu$, and the exact ε-memory is defined as before.

**Proposition 2.2.** Let $W$ be an objective. If $W$ has $\epsilon$-memory $< \mu$, for some cardinal $\mu$, then there is some cardinal $\alpha < \mu$ such that $W$ has $\epsilon$-memory $\le \alpha$.

Therefore, for $\epsilon$-memory and in the case of objectives, we can restrict our study to non-strict inequalities without loss of generality. Moreover, the exact $\epsilon$-memory of an objective is always defined.

*Proof of Proposition 2.2.* Suppose by contradiction that $W$ has $\epsilon$-memory $< \mu$ and that it has $\epsilon$-memory $> \alpha$ for all $\alpha < \mu$. By definition of having $\epsilon$-memory $> \alpha$, for each $\alpha < \mu$ there is a game in which Eve can win, but she cannot do so with strategies with $\epsilon$-memory $\le \alpha$. Let $\mathcal{G}_\alpha = (G_\alpha, V_{Eve,\alpha}, v_{0,\alpha}, \text{val})$ be such a game, for $\alpha < \mu$. We take the disjoint union of all these games and we let Adam choose the initial vertex among $v_{0,\alpha}$. Formally, let $\mathcal{G} = (G, V_{Eve}, v_0, \text{val})$, where:

* $V(G) = \bigsqcup_{\alpha < \mu} V(G_\alpha) \cup \{v_0\}$,

* $V_{Eve} = \bigsqcup_{\alpha < \mu} V_{Eve,\alpha}$,

* $E(G) = \bigsqcup_{\alpha < \mu} E(G_\alpha) \cup \{v_0 \xrightarrow{\epsilon} v_{0,\alpha} \mid \alpha < \mu\}$.

First we remark that Eve wins this game: no matter Adam's choice, after the first $\epsilon$-move the play will take place in some game $\mathcal{G}_\alpha$, where Eve can use a winning strategy. Let $S$ be a winning $\epsilon$-strategy over some set $M$, $|M| = \alpha < \mu$ (that exists since we have supposed that $W$ has $\epsilon$-memory $< \mu$). Let $s_0 = (v_0, m_0)$. Since $(v_0, m_0) \xrightarrow{\epsilon} (v_{0,\alpha}, m_0)$, and $S$ is winning, all paths from $(v_{0,\alpha}, m_0)$ satisfy $W$. Therefore, the restriction of $S$ to $\{(v, m) \mid v \in V(G_\alpha)\}$ is a winning $\epsilon$-strategy with $\epsilon$-memory $\le \alpha$, which contradicts the fact that Eve cannot win $\mathcal{G}_\alpha$ using strategies with $\epsilon$-memory $\le \alpha$. $\square$

Note that by definition, a chromatic strategy over $M$ with update function $\delta$ is an $\epsilon$-strategy if and only if for all $m \in M$ it holds that $\delta(m, \epsilon) = m$. We call such a strategy an $\epsilon$-chromatic strategy. A valuation val has $\epsilon$-chromatic memory $< \mu$ (resp. $\leq \mu$) if in all $\epsilon$-games with valuation val$^\epsilon$, the value is attained by $\epsilon$-chromatic strategies with memory $< \mu$ (resp. $\leq \mu$). The exact $\epsilon$-chromatic memory is defined analogously.

Whenever we want to emphasise that we consider games (resp. strategies, memory) without $\epsilon$, we might add the adjective $\epsilon$-free.

## 2.3. Monotonicity and universality.

**Monotonicity.** A partially ordered graph $(G, \le)$ is *monotone* if

$$u \ge v \xrightarrow{c} v' \ge u' \text{ implies } u \xrightarrow{c} u' \text{ in } G.$$

A partially ordered graph $(G, \le)$ is called *well-monotone* if it is monotone and it is well-founded as a partial order. We say that the *width* of a partially ordered graph is $< \mu$ (resp. $\le \mu$) if it does not contain antichains of size $\mu$ (resp. of size strictly greater than $\mu$).
**ε-separation.** An ε-separated monotone graph over a set M is a C^ε-graph G such that $\epsilon \to$ defines a partial order making G monotone ($v \le v' \iff v' \xrightarrow{\epsilon} v \in E(G)$), and moreover $V(G)$ is partitioned into $(V_m)_{m \in M}$ such that for all $m \in M$, $\epsilon \to$ induces a total order over $V_m$, and there are no ε-edges between different parts: $v \xrightarrow{\epsilon} v' \in E(G)$ implies that $v, v' \in V_m$ for some $m \in M$. See Figure 4. We define the breadth of such a graph as $|M|$.

<figure><img src="image_7.png" /><figcaption>Figure 4: An ε-separated chromatic monotone graph of breadth 2. Note that $\epsilon \to$ defines a total order on each $V_i$ (edges following from transitivity are not represented). Many edges which follow from monotonicity are not depicted, the dotted edges give a few examples.</figcaption></figure>

An ε-separated monotone graph G over M is chromatic if there is a map $\delta: M \times C \to M$ such that for all $v \xrightarrow{\delta} v' \in E(G)$ with $v \in V_m$ and $v' \in V_{m'}$ we have $m' = \delta(v, m)$. We also say in this case that $\delta$ is the update function of G.

**Universality.** Given a C-valuation val, a C-graph G and a cardinal $\kappa$, we say that G is $(\kappa, \text{val})$-universal$^6$ if for all C-trees T of cardinality $< \kappa$, there exists a morphism $\phi: T \to G$ such that

$$ \text{val}_G(\phi(t_0)) \le \text{val}_T(t_0), $$

where $t_0$ is the root of T. We say that $\phi$ preserves the value at the root to refer to this property (we remark that, in that case, $\text{val}_G(\phi(t_0)) = \text{val}_T(t_0)$, since the other inequality always holds).

**Remark 2.3.** In the above definition, for a graph to be universal, it needs to embed all trees (up to a given cardinality bounds), and not all graphs as in the case of positionality [Ohl23]. For (totally) well-ordered graphs, that is, in the case of positionality, this does not make a difference; however for the current study of memory, this difference is important. An example where the definition with graphs is too constrained to capture memory is given in Proposition 5.5.

**Remark 2.4.** We remark that if U is a $(\kappa, \text{val}^\epsilon)$-universal graph, then the graph $U'$ obtained by removing the edges labelled by $\epsilon$ is $(\kappa, \text{val})$-universal. Moreover, if U is an ε-separated monotone graph of breadth $\mu$, then $U'$ is a monotone graph of width $\le \mu$.

<footnote>$^6$This definition is tailored to the general setting of quantitative valuations, for which we are able to present most results. When specifying to objectives (more precisely, to prefix-increasing objectives) the concept of universality can be simplified without loss of generality. This will be the object of Section 3.4.2.</footnote>
### 3. MAIN CHARACTERISATION RESULTS

In this section, we state (Section 3.1) and prove (Sections 3.2 and 3.3) our two main results, Theorems 3.1 and 3.2. This is followed by additional general results (Section 3.4).

**3.1. Statement of the results.** We start with our characterisations of $\varepsilon$-memory and $\varepsilon$-chromatic memory via (chromatic) $\varepsilon$-separated universal graphs.

**Theorem 3.1.** Let $\text{val}$ be a valuation. If for all cardinals $\kappa$ there exists an $\varepsilon$-separated (chromatic) and well-monotone ($\kappa, \text{val}^\varepsilon$)-universal graph of breadth $\le \mu$, then $\text{val}$ has $\varepsilon$-chromatic-memory $\le \mu$. The converse holds if $\text{val}$ is an objective (in both the chromatic and non-chromatic cases).

As explained by Proposition 2.2, strict inequalities, though they give more precise statements, are irrelevant for $\varepsilon$-memory. Thus the use of non-strict inequalities in the statement above is not restrictive.

We state our second result in terms of strict inequalities, which is relevant in the case of $\varepsilon$-free memory, and allows for more precision. However, we do not have a converse statement (as discussed in the introduction, the converse cannot hold, see also Figure 2 and Proposition 5.2).

**Theorem 3.2.** Let $\text{val}$ be a valuation. If for all cardinals $\kappa$ there exists a well-monotone ($\kappa, \text{val}$)-universal graph of width $< \mu$, then $\text{val}$ has $\varepsilon$-free memory $< \mu$.

As we will see in Section 3.4.1, the two results above collapse for finite cardinals $\mu$.

**Remark 3.3.** We remark that we say that the ($\varepsilon$-)chromatic memory of an objective is $\le \mu$ if for all games, the value can be attained with a chromatic product strategy over some structure $M$, $|M| \le \mu$, with update function $\delta$. We could ask if it is possible to modify the order of the quantifiers in this definition, that is, if we could fix the structure $M$ and its update function in advance, regardless of the game. The notion obtained in that way is called *arena-independent memory* in the recent literature [BRO+22].

Over $\varepsilon$-games, the size of a minimal arena-independent memory for an objective coincide with its $\varepsilon$-chromatic memory (this is proved for the case of finite memory in [Kop08, Proposition 8.9]). We note that this result can be easily derived from Theorem 3.1 and its proof: the existence of an $\varepsilon$-separated chromatic universal graph over the structure $M$ implies that $M$ is an arena-independent memory (see Section 3.2), and the existence of such a graph is guaranteed by the implication from right to left of this theorem.

We do not know whether the sizes of a minimal $\varepsilon$-free arena-independent memory and the $\varepsilon$-free chromatic memory also coincide.

**3.2. From structure to finite memory.** The goal of this section is to prove Theorem 3.2 and the first implication in Theorem 3.1. The two proofs are very similar; we start with Theorem 3.2.

*Proof of Theorem 3.2.* Let $\text{val}: C^\omega \to X$ be a valuation, $G = (G, V_{\text{Eve}}, v_0, \text{val})$ a game and $\mathcal{T} = (T, \pi_\tau, t_0)$ be a strategy for $G$ such that $T$ is a tree. Our aim is to define a strategy with memory $< \mu$ and value $\le \text{val}(\mathcal{T})$; this proves that $\text{val}$ has memory $< \mu$ thanks to Lemma 2.1.
<figure><img src="image_8.png" /><figcaption>Figure 5: An illustration for the construction of the bounded-memory strategy $S$ in the proof of Theorem 3.2.</figcaption></figure>

Take a well-monotone ($|T|$, val)-universal graph ($U, \leq$) with width $< \mu$, and consider a morphism $\phi: T \to U$ preserving the value at the root, $\text{val}_T(t_0) = \text{val}_U(\phi(t_0))$. For each $v \in V(G)$, we consider the set $M_v \subseteq V(U)$ of minimal elements of $\phi(\pi_T^{-1}(v))$ (see Figure 5). We define our strategy $S = (S, \pi_S, s_0)$ over

$$V(S) = \bigsqcup_{v \in V(G)} \{v\} \times M_v,$$

with projection $\pi_S: (v, m) \mapsto v$, and let $s_0 = (v_0, m_0)$ where $m_0 \in M_{v_0}$ is an element below $\phi(t_0)$ in $V(U)$. Note that for all $v \in V(G)$, $M_v$ is an antichain of $V(U)$ and therefore $|\pi_S^{-1}(v)| = |M_v| < \mu$, as required.

For each element $(v, m) \in V(S)$, fix a choice of a $t_{(v,m)} \in \pi_T^{-1}(v)$ such that $\phi(t) = m$. We now let

$$E(S) = \{(v, m) \xrightarrow{c} (v', m') \mid \exists t' \in \pi_T^{-1}(v'), t_{(v,m)} \xrightarrow{c} t' \in E(T) \text{ and } \phi(t') \geq m'\},$$

which concludes the definition of $S$.

Let us verify that $S$ is indeed a strategy over $G$. It is clear that $\pi_S(s_0) = v_0$. Now observe that for any $(v, m) \in V(S)$, and any edge $t_{(v,m)} \xrightarrow{c} t' \in E(T)$, if we denote $v' = \pi_T(t')$, there is an element $m' \leq \phi(t')$ in $M_{v'}$. This induces an edge $(v, m) \xrightarrow{c} (v', m') \in E(S)$. This implies, since $T$ is a graph (it has no sink), that $S$ is a graph. Moreover, for all $v \in V_{Adam}$ and outgoing edge $v \xrightarrow{c} v' \in E(G)$, since $T$ is a strategy $t_{(v,m)}$ has an outgoing edge in $T$ towards some $t'$ with $\pi_T(t') = v'$, thus by the above observation, $(v, m)$ has an outgoing edge in $S$ towards an element $(v', m')$ (which has projection $\pi_S(v', m') = v'$, as required) and $S$ is a strategy.
There remains to see that $\mathrm{val}(S) \le \mathrm{val}(\mathcal{T})$. We will in fact prove that $\psi : (v, m) \mapsto m$ is a morphism from $S$ to $U$, which implies that

$$ \mathrm{val}(S) = \mathrm{val}_S(s_0) \le \mathrm{val}_U(\psi(s_0)) = \mathrm{val}_U(m_0) \le \mathrm{val}_U(\phi(t_0)) = \mathrm{val}(\mathcal{T}), $$

the wanted result. Let $(v, m) \xrightarrow{c} (v', m') \in E(S)$, we aim to prove that $m \xrightarrow{c} m' \in E(U)$. Let $t'$ be such that $\pi_{\mathcal{T}}(t') = v'$, $t_{(v,m)} \xrightarrow{c} t'$ and $\phi(t') \ge m'$. Since $\phi$ is a morphism we have in $U$

$$ m = \phi(t_{(v,m)}) \xrightarrow{c} \phi(t') \ge m', $$

thus by monotonicity, $m \xrightarrow{c} m' \in E(U)$.

<figure><img src="image_9.png" /></figure>

The proof of the first implication in Theorem 3.1 is essentially the same, with a few minor adjustments. We spell it out for completeness.

**Proof of** $\implies$ **in Theorem 3.1.** Let $\mathrm{val} : C^\omega \to X$ be a valuation, $\mathcal{G} = (G, V_{\mathrm{Eve}}, v_0, \mathrm{val}^\epsilon)$ an $\epsilon$-game and $\mathcal{T} = (T, \pi_T, t_0)$ a strategy for $\mathcal{G}$ such that $T$ is a tree. Our aim is to define an $\epsilon$-strategy with memory $\le \mu$ and value $\le \mathrm{val}(\mathcal{T})$. Take an $\epsilon$-separated well-monotone $(|T|, \mathrm{val}^\epsilon)$-universal graph $(U, \xrightarrow{\epsilon} \mathcal{T})$ with partition $(U_m)_{m \in M}$ of width $|M| \le \mu$, and consider a morphism $\phi : T \to U$ preserving the value at the root. We define the product strategy $S = (S, \pi_S, s_0)$ by

$$ V(S) = \{(v, m) \in V(G) \times M \mid \phi(\pi_T^{-1}(v)) \cap U_m \neq \emptyset\}, $$

with $s_0 = (v_0, m_0)$, where $m_0$ is such that $\phi(t_0) \in U_{m_0}$, and with projection $\pi_S : (v, m) \mapsto v$. To define $E(S)$, we pick for each $(v, m) \in V(S)$ an element $t_{(v,m)} \in V(T)$ such that $\phi(t_{(v,m)}) = \min\{\phi(\pi_T^{-1}(v)) \cap U_m\}$, and let

$$ E(S) = \{(v, m) \xrightarrow{c} (v', m') \mid \exists t' \in \pi_T^{-1}(v'), t_{(v,m)} \xrightarrow{c} t' \in E(T) \text{ and } \phi(t') \in U_{m'}\}. $$

We verify that $S$ is indeed a strategy over $\mathcal{G}$. By definition, we have $\pi_S(s_0) = v_0$. Observe that for any $(v, m) \in V(S)$, and any edge $t_{(v,m)} \xrightarrow{c} t' \in E(T)$, there is an edge $(v, m) \xrightarrow{c} (v', m') \in E(S)$ where $v' = \pi_T(t')$ and $m'$ is such that $\phi(t') \in U_{m'}$. This implies that $S$ is a strategy since $\mathcal{T}$ is.

We now prove that $\psi : (v, m) \mapsto \min\{\phi(\pi_T^{-1}(v)) \cap U_m\}$ is a morphism from $S$ to $U$. This implies

$$ \mathrm{val}(S) = \mathrm{val}_S(s_0) \le \mathrm{val}_U(\psi(v_0, m_0)) \le \mathrm{val}_U(\phi(t_0)) = \mathrm{val}(\mathcal{T}), $$

the wanted result. Let $(v, m) \xrightarrow{c} (v', m') \in E(S)$, and let $t'$ be such that $\pi_T(t') = v'$, $t_{(v,m)} \xrightarrow{c} t' \in E(T)$ and $\phi(t') \in U_{m'}$. We have by definition $\phi(t_{(v,m)}) = \psi(v, m)$ and $\phi(t') \ge \psi(v', m')$, therefore we conclude by monotonicity of $U$ that $\psi(v, m) \xrightarrow{c} \psi(v', m')$. Finally, remark that if $c = \epsilon$, since $\psi(v, m) \in U_m$ and $\psi(v', m') \in U_{m'}$ and there are no $\epsilon$-edges in $U$ between different partitions, it must be that $m = m'$ which concludes our proof for the non-chromatic case: $S$ is indeed an $\epsilon$-strategy.

For the chromatic case, it suffices to show in the construction above that if $U$ is in fact chromatic, then so is the constructed strategy $S$. For this, we observe that the morphism $\psi$ above maps $(v, m) \in V(S)$ to a vertex in $U_m$, therefore if $(v, m) \xrightarrow{c} (v', m') \in E(S)$ and $\delta$ is the update function of $U$, it must be that $\delta(m, c) = m'$. We conclude that $S$ is indeed a chromatic strategy with update function $\delta$.

<figure><img src="image_10.png" /></figure>
**3.3. From finite memory to structure.** In this section, we prove the converse implication in Theorem 3.1. The main difficulty lies in proving the following result, which holds at the level of valuations, and which we refer to as a structuration lemma for $C^\epsilon$-trees.

**Lemma 3.4 (Structuration of $C^\epsilon$-trees).** Let $val: C^\omega \to X$ be a valuation with $\epsilon$(-chromatic)-memory $\le \mu$ and let $T$ be a $C^\epsilon$-tree with root $t_0 \in V(T)$. There exists an $\epsilon$-separated well-monotone (chromatic) graph $U$ of breadth $\le \mu$ and a morphism $T \to U$ preserving the value at the root.

Before proving the lemma, we show that it implies the Theorem.

*Proof of ⇐ in Theorem 3.1 assuming Lemma 3.4.* We consider an objective $W \subseteq C^\omega$ which has $\epsilon$-memory $\le \mu$, and fix a cardinal $\kappa$. We consider the disjoint union of all $C^\epsilon$-trees of cardinality $< \kappa$ whose roots satisfy $W^\epsilon$, up to isomorphism, and we let $T$ be the tree with root $t_0$ obtained from this disjoint union by adding an $\epsilon$-edge from $t_0$ to the root of each tree (see Figure 6). Note that $t_0$ satisfies $W^\epsilon$.

<figure><img src="image_11.png" /><figcaption>Figure 6: The tree on which Lemma 3.4 is applied.</figcaption></figure>

We now apply Lemma 3.4 to $T$ and obtain an $\epsilon$-separated well-monotone (chromatic) graph $U$ of breadth $\le \mu$ with a morphism $\phi: T \to U$ such that $\phi(t_0)$ satisfies $W^\epsilon$ in $U$. There remains to prove that $U$ is $(\kappa, W^\epsilon)$-universal. Consider a $C^\epsilon$-tree $T'$ of cardinality $< \kappa$ and whose root satisfies $W^\epsilon$. By definition of $T$, there is $t'$ in $T$ with $t_0 \stackrel{\epsilon}{\to} t'$ such that the tree rooted at $t'$ in $T$ is isomorphic to $T'$. We then obtain a morphism $\phi': T' \to U$ simply as a restriction of $\phi$ (composed with the isomorphism). Since $\phi(t_0)$ satisfies $W^\epsilon$ in $T$, so does $\phi(t')$, and therefore $\phi'$ preserves the value at the root, as required.

To accommodate trees whose root do not satisfy $W$, in the non-chromatic case it suffices to add an additional vertex $\top$ (in any chosen part $U_m$) with $c$-edges towards all $U_m$ (including itself) for all $c \in C^\epsilon$. This preserves being $\epsilon$-separated well-monotone of breadth $\le \mu$, does not increase the value of vertices $\ne \top$, and allows to embed (while preserving the value at the root) any tree $T'$ whose root does not satisfy $W$ simply by mapping everything to $\top$.

The chromatic case requires being slightly more careful. Let $\delta$ be the update function of $U$. For each $m \in M$ we add a vertex $\top_m \in U_m$, with $c$-edges towards all $U_{m'}$ (including $\top_{m'}$) whenever $\delta(m, c) = m'$. This preserves being $\epsilon$-separated, well-monotone, chromatic and of breadth $\le \mu$, and does not increase the value of vertices $\notin \{\top_m | m \in M\}$. Now, if $T'$ is a tree whose root $t'_0$ does not satisfy $W$, we easily embed it in a top-down fashion, by mapping $t'_0$ to $\top_{m_0}$ (for any choice of $m_0$), and mapping $t' \in V(T)$ to $\delta^*(m_0, w)$, where $w$ is the label of the unique path from $t'_0$ to $t'$ in $T$. $\square$

We now prove Lemma 3.4; our proof extends the one of [Ohl23, Theorem 3.3].
Proof of Lemma 3.4. Let $\text{val}: C^\omega \to X$ be a valuation with $\varepsilon$(-chromatic)-memory $\le \mu$ and $T$ be a $C^\varepsilon$-tree with root $t_0$. We consider the $\varepsilon$-game $\mathcal{G} = (G, V_{\text{Eve}}, v_0, \text{val}^\varepsilon)$ obtained by adding an Eve vertex for each non-empty set $A$ of vertices of $T$, and $\varepsilon$-edges back and forth from $t$ to $A$ whenever $t \in A$, with the control given to Adam over $V(T)$. Formally, it is given by

$$V(G) = V(T) \cup \mathcal{P}^{\neq \emptyset}(V(T))$$

$$V_{\text{Eve}} = \mathcal{P}^{\neq \emptyset}(V(T))$$

$$E(G) = E(T) \cup \{t \xrightarrow{\varepsilon} A \mid t \in A\} \cup \{A \xrightarrow{\varepsilon} t \mid t \in A\},$$

and $v_0 = t_0$. See Figure 7 for an illustration.

<figure><img src="image_12.png" /><figcaption>Figure 7: The game $\mathcal{G}$.</figcaption></figure>

We claim that the value of $\mathcal{G}$ is $\le \text{val}_T(t_0)$. Indeed, consider the strategy for Eve which, whenever arriving at $A \in V_{\text{Eve}}$ via an edge $t \xrightarrow{\varepsilon} A$, follows the edge $A \xrightarrow{\varepsilon} t$ back towards $t$. Consider an infinite path $\pi$ from $t_0$ in that strategy, and let $\pi'$ be obtained from $\pi$ by removing all occurrences of $t \xrightarrow{\varepsilon} A \xrightarrow{\varepsilon} t$. Note that $\pi'$ defines a path from $t_0$ in $T$. There are two cases.

* If $\pi'$ is infinite, then by neutrality of $\varepsilon$ it has the same value as $\pi$.

* If $\pi'$ is finite, then any continuation of $\pi'$ in $T$ has value $\ge \text{val}^\varepsilon(\pi)$ by definition of $\text{val}^\varepsilon$.

This proves that for each infinite path $\pi$ from $t_0$ in the strategy, there exists an infinite path of value $\ge \text{val}^\varepsilon(\pi)$ from $t_0$ in $T$, and thus $\text{val}^\varepsilon(\mathcal{G}) \le \text{val}_T(t_0)$.

Since $\text{val}$ has $\varepsilon$(-chromatic)-memory $\le \mu$, there exists an $\varepsilon$(-chromatic) strategy $S = (S, \pi_S, s_0)$ over $\mathcal{G}$ with value $\text{val}^\varepsilon(S) = \text{val}^\varepsilon(\mathcal{G})$ and memory $\le \mu$. By definition we have $V(S) \subseteq V(G) \times M$ with $|M| \le \mu$, $\pi_S : (v, m) \mapsto v$ and $(v, m) \xrightarrow{\varepsilon} (v', m') \in E(S)$ implies $m = m'$. In particular, we have $s_0 = (t_0, m_0)$ for some $m_0 \in M$.

For each $(t, m) \in V(S)$ with $t \in V(T)$, and each edge $t \xrightarrow{c} t' \in E(T)$, it holds that $t \xrightarrow{c} t' \in E(G)$ and $t \in V_{\text{Adam}}$ therefore there is $(t', m') \in V(S)$ with $(t, m) \xrightarrow{c} (t', m') \in E(S)$ since $S$ is a strategy. This allows to define a morphism $\phi: T \to S$ by proceeding top-down: we set $\phi(t_0) = s_0 = (t_0, m_0)$, and assuming $\phi(t) = (t, m)$ is defined and $t \xrightarrow{c} t' \in E(T)$ we let $\phi(t') = (t', m')$ with $(t, m) \xrightarrow{c} (t', m') \in E(S)$. Since $\text{val}^\varepsilon(S) = \text{val}^\varepsilon(\mathcal{G})$, it holds that $\phi$ preserves the value at the root; moreover, note that the image of $\phi$ is included in $V(T) \times M \subseteq V(S)$.

Observe that for each $(t, m) \in V(S)$ with $t \in V(T)$, and each $A \ni t$, since $t \xrightarrow{\varepsilon} A \in E(G)$ and $t \in V_{\text{Adam}}$, the edge $(t, m) \xrightarrow{\varepsilon} (A, m)$ belongs to $E(S)$. Moreover, for each $(A, m) \in V(S)$,
with $A \in \mathcal{P}^{\neq\emptyset}(V(T))$ there is an element $t_{(A,m)} \in A$ such that $(A, m) \xrightarrow{\epsilon} (t_{(A,m)}, m) \in E(S)$; we fix such a $t_{(A,m)}$ for each $(A, m)$. Combining these two observations, we have for each $(t, m) \in V(S)$ with $t \in V(T)$ and each $A \ni t$, the edges

$$ (t, m) \xrightarrow{\epsilon} A \xrightarrow{\epsilon} (t_{(A,m)}, m) $$

in $E(S)$.

We now let $U^{(0)}$ be the graph over $V(U^{(0)}) = V(S) \cap (V(T) \times M)$ given by

$$ E(U^{(0)}) = E(S) \cap [V(U^{(0)}) \times C \times V(U^{(0)})] \cup \{(t, m) \xrightarrow{\epsilon} (t_{A,m}, m) \mid t \in A\}. $$

In words, the graph $U^{(0)}$ is obtained by first restricting $S$ to $V(T) \times M$, and then adding all edges $(t, m) \xrightarrow{\epsilon} (t_{(A,m)}, m)$. Note that $\phi: T \to S$ defined above restricts to a morphism $\phi^{(0)}: T \to U^{(0)}$. Moreover, any path $\pi$ from $s_0$ in $U^{(0)}$ can be turned to a path $\pi'$ from $s_0$ in $S$ by replacing each occurrence of edges $(t, m) \xrightarrow{\epsilon} (t_{(A,m)}, m)$ by $(t, m) \xrightarrow{\epsilon} (A, m) \xrightarrow{\epsilon} (t_{(A,m)}, m)$. Since the path $\pi'$ obtained in this way has the same value as $\pi$, we have $\text{val}_{U^{(0)}}(s_0) \le \text{val}_S(s_0) = \text{val}_T(t_0)$; stated differently $\phi^{(0)}$ preserves the value at the root. Since it is the case in $S$, and we added only $\epsilon$-edges which preserve the memory state $m$, it holds that $(t, m) \xrightarrow{\epsilon} (t', m') \in E(U^{(0)})$ implies $m = m'$.

Note that for each $(t, m) \in V(U^{(0)})$ it must be that $t_{\{(t),m\}} = t$ (since by definition $t_{(A,m)} \in A$), and thus there is a loop $(t, m) \xrightarrow{\epsilon} (t, m) \in E(U^{(0)})$. We then let $U^{(1)}$ be given by $V(U^{(1)}) = V(U^{(0)})$ and

$$ E(U^{(1)}) = \{u \xrightarrow{c} u' \mid \exists v, v' \in V(U^{(0)}), u \xrightarrow{\epsilon^*} v \xrightarrow{c} v' \xrightarrow{\epsilon^*} u' \text{ in } U^{(0)}\}, $$

where the notation $x \xrightarrow{\epsilon^*} y$ means that there exists a path of $\epsilon$-edges from $x$ to $y$. By the observation above, it holds that $E(U^{(0)}) \subseteq E(U^{(1)})$ or stated differently the identity is a morphism from $U^{(0)}$ to $U^{(1)}$; we thus obtain a morphism $\phi^{(1)}: T \to U^{(1)}$ by composition. We now argue that $\phi^{(1)}$ preserves the value at the root: any path $\pi$ from $s_0$ in $U^{(1)}$ can be transformed into a path $\pi'$ in $U^{(0)}$ with same value by replacing occurrences of $u \xrightarrow{c} u'$ by $u \xrightarrow{\epsilon^*} v \xrightarrow{c} v' \xrightarrow{\epsilon^*} u'$, thus $\text{val}_{U^{(1)}}(s_0) \le \text{val}_{U^{(0)}}(s_0) \le \text{val}_T(t_0)$. Moreover, $\epsilon$-edges in $U^{(1)}$ cannot modify the memory state $m$ since this is the case of $\epsilon^*$-paths in $U^{(0)}$.

Observe now that it holds that $u \xrightarrow{\epsilon} v \xrightarrow{c} v' \xrightarrow{\epsilon} u'$ in $U^{(1)}$ implies $u \xrightarrow{c} u' \in E(U^{(1)})$. Applying to $c = \epsilon$ gives transitivity of $\xrightarrow{\epsilon}$. Moreover, defining the partition of $V(U^{(1)})$ by $(V_m^{(1)})_{m \in M}$ with $V_m^{(1)} = V(U^{(1)}) \cap (V(T) \times \{m\})$, we have that for each $m \in M$ and each non-empty subset $A \times \{m\}$ of $V_m^{(1)}$, for each $(t, m) \in A \times \{m\}$ there is an $\epsilon$-edge in $E(U^{(1)})$ towards $(t_{(A,m)}, m)$. This implies that $\xrightarrow{\epsilon}$ induces a well-founded total preorder over $V_m^{(1)}$, satisfying the monotonicity axiom.

The only remaining caveat is that $\xrightarrow{\epsilon}$ is not necessarily antisymmetric over $V(U^{(1)})$. However, in $U^{(1)}$, vertices $v, v'$ such that both $v \xrightarrow{\epsilon} v'$ and $v' \xrightarrow{\epsilon} v$ have the same incoming and outgoing edges. Defining such vertices to be $\sim$-equivalent, we thus let $U^{(2)}$ be given over $V(U^{(2)}) = V(U^{(1)})/\sim$ by

$$ E(U^{(2)}) = \{[v] \xrightarrow{c} [v'] \mid v \xrightarrow{c} v' \in E(U^{(1)})\}, $$

where $[v]$ is the $\sim$-class of $v$; note that this is well defined since $v \xrightarrow{c} v' \in E(U^{(1)})$ does not depend on the choices of representatives $v$ and $v'$ in $[v]$ and $[v']$. It is easy to verify that the morphism $v \mapsto [v]$ preserves all values from $U^{(1)}$ to $U^{(2)}$, and that $U^{(2)}$ is an $\epsilon$-separated
monotone graph of width $\mu$, with the partition $(V_m^{(2)})_{m \in M}$ defined by $V_m^{(2)} = V_m^{(1)} / \sim$. This
concludes the proof in the non-chromatic setting.

For the chromatic case, there remains to verify that $U^{(2)}$ is chromatic. We let $\delta : M \times C \to M$ be the update function of $S$. Let $[u] \xrightarrow{c} [u'] \in E(U^{(2)})$, we will show that $\delta$ witnesses the fact that $U^{(2)}$ is chromatic. Unraveling the definitions, we obtain that $u \xrightarrow{c} u' \in E(U^{(1)})$, and in turn $u \xrightarrow{\varepsilon^*} v \xrightarrow{c} v' \xrightarrow{\varepsilon^*} u'$ in $U^{(0)}$ for some $v, v' \in V(U^{(0)})$. Since in $U^{(0)}$, $\varepsilon$-edges preserve the memory state, we get that $u$ and $v$, as well as $u'$ and $v'$ have the same memory state; let us write them $m$ and $m'$. We aim to show that $m' = \delta(m, c)$. If $c = \varepsilon$, there is nothing to prove, we already know that $\varepsilon$-edges preserve the memory state in $U^{(2)}$. Otherwise, by definition of $U^{(0)}$ we get that $v \xrightarrow{c} v' \in E(S)$, which yields $m' = \delta(m, c)$ as required. $\square$

**3.4. Further results.** Before going to applications in subsequent sections, we prove a few further general results that are useful for constructing universal graphs. We start by proving (Section 3.4.1) that in the case of memory $\le m$ for some finite $m \in \mathbb{N}$, and with some further technical assumptions, our two notions of universal structures (well-monotone graphs with bounded antichains on one hand, and $\varepsilon$-separated well-monotone graphs with bounded breadth) collapse.

We proceed to show how our definitions instantiate in the important special cases of prefix-increasing (Section 3.4.2) and prefix-independent (Section 3.4.3) objectives (these are defined later). Last, we show (Section 3.4.4) how the convenient notion of almost universality (which serves as a lever for deriving universality results) from [Ohl23] adapts to the setting at hands.

We urge the reader to jump to Section 4 and come back to 3.4 when required.

3.4.1. *Finitely bounded antichains determine the $\varepsilon$-memory.* Dilworth's Theorem (c.f. Appendix A) states that if the size of the antichains of an ordered set $(P, \le)$ is bounded by a finite number $k$, then $P$ can be decomposed in $k$ disjoint chains [Dil50]. Therefore (assuming well-foundedness of the set of values), this allows to construct $\varepsilon$-separated universal structures from arbitrary monotone ones, whenever we have a finite bound on the width.

**Proposition 3.5.** Let $\text{val} : C^\omega \to X$ be a valuation, and $m \in \mathbb{N}$; we further assume that $X$ is well-founded. If for all cardinals $\kappa$ there exists a well-monotone graph which is (κ, val)-universal and has width $\le m$, then for all cardinals $\kappa$ there is also an $\varepsilon$-separated well-monotone (κ, val$^\varepsilon$)-universal graph of breadth $\le m$, and therefore val has $\varepsilon$-memory $\le m$.

Unfortunately, proving this proposition requires dealing with some slight technical complications arising from creation of sinks when contracting $\varepsilon$'s in an infinite tree. This is what leads to the assumption that $X$ is well-founded, we do not know whether it can be dropped. Note however that objectives are valuations with $X = \{\perp, \top\}$, which is well-founded, and moreover many other interesting examples of valuations have well-founded sets of values (for instance, energy valuations over $\mathbb{N}$).

Proposition 3.5 is very useful in practice (see examples in Section 4) for establishing finite $\varepsilon$-memory: it suffices to construct universal structures with bounded width, which is often easier in practice than $\varepsilon$-separated structures. One can also see the result in a negative
light: for finite bounds (for instance, $\omega$-regular objectives), one cannot use Theorem 3.2 to
derive $\varepsilon$-free memory upper bounds smaller than the $\varepsilon$-memory.

*Proof.* Let $(G, \leq)$ be a well-monotone $(\kappa, \text{val})$-universal $C$-graph of width $\leq m$. Applying Dilworth's Theorem yields a partition of $V(G)$ into $(V_j)_{j \in m}$ so that the restriction of $\leq$ to each $V_j$ is a total order. We let $G^\varepsilon$ be the graph over $V(G)$ defined by adding $\xrightarrow{\varepsilon}$'s according to this decomposition, that is,

$$
E(G^{\varepsilon}) = E(G) \cup \{v \xrightarrow{\varepsilon} v' \mid v \ge v' \text{ in } G \text{ and } \exists j \in m \text{ such that } v, v' \in V_j\}.
$$

Note that $G^\epsilon$ is indeed an $\epsilon$-separated monotone graph over $m$, as required. We first prove
that values in $G^\epsilon$ are the same as in $G$, that is, for any $v \in V(G) = V(G^\epsilon)$ it holds that

$$
\mathrm{val}_G(v) = \mathrm{val}^{\epsilon}_{G^{\epsilon}}(v).
$$

We remark that $\text{val}_G(v) \le \text{val}^\epsilon_{G^\epsilon}(v)$, since $G$ is a subgraph of $G^\epsilon$. For the other inequality, let $v \in V(G)$ and consider a path $\pi : v_0 \xrightarrow{c_0} v_1 \xrightarrow{c_1} \dots$ from $v = v_0$ in $G^\epsilon$, our aim is to construct a path from $v$ in $G$ with value larger than $\pi$; for this we proceed in two steps. First, we replace in $\pi$ any block of the form

$$
v_i \xrightarrow{\epsilon} v_{i+1} \xrightarrow{\epsilon} \dots \xrightarrow{\epsilon} v_{j-1} \xrightarrow{c} v_j,
$$

where $c \in C$, by

$v_i \xrightarrow{c} v_j.$

This does not increase the val$^\epsilon$-value by definition, and yields a path $\pi'$ in $G^\epsilon$ by monotonicity.
Now if the original path $\pi$ had infinitely many occurrences of colours in $C$, we are done;
otherwise $\pi'$ is of the form $\pi'_0\pi'_1$, where $\pi'_0$ is a finite path avoiding $\epsilon$-edges whereas $\pi'_1$ is an
infinite path comprised only of $\epsilon$-edges. Note that $\pi'_0$ is thus a finite path from $v$ in $G$, let $v'$
denote its endpoint. Now append to $\pi'_0$ any infinite path starting from $v'$ in $G$, which yields
a path $\pi''$ in $G$ with value $\ge \text{val}^\epsilon(\pi)$, by definition of val$^\epsilon$.

We now proceed to proving $(\kappa, \text{val}^{\epsilon})$-universality of $G^{\epsilon}$: let $T^{\epsilon}$ be a $C^{\epsilon}$-tree of cardinality $< \kappa$ and let $t_0 \in V(T^{\epsilon})$ denote its root. We first remove $\xrightarrow{\epsilon}$'s from $T^{\epsilon}$ by contracting them, formally we let $T$ be the $C$-pretree given over

$$
V(T) = \{t \in V(T^{\epsilon}) \mid \text{the unique path from } t_0 \text{ to } t \text{ in } T^{\epsilon} \text{ does not end with an } \epsilon\text{-edge}\}
$$

by

$$
E(T) = \{t \xrightarrow{c} t' \mid t \xrightarrow{\epsilon^*} t'' \xrightarrow{c} t' \text{ in } T\}.
$$

Note that $T$ is rooted at $t_0 \in V(T)$, and that there may be sinks in $T$, namely, the vertices
from which all paths visit only $\epsilon$-edges in $T^\epsilon$; let

$$
\begin{align*}
S &= \{t \in V(T) \mid t \text{ is a sink in } T\} \\
  &= \{t \in V(T) \mid \text{ all paths from } t \text{ in } T^{\epsilon} \text{ see only } \epsilon\text{-edges}\}.
\end{align*}
$$

For each $s \in S$, let $u_s \in C^*$ be the coloration of the unique path from $t_0$ to $s$ in $T$, and let $w_s \in C^\omega$ be an infinite word such that

$$
\mathrm{val}^{\epsilon}(u_s \epsilon^{\omega}) = \mathrm{val}(u_s w_s),
$$

whose existence is guaranteed by well-foundedness of X and the definition of val$^\epsilon$.

We then append to each sink $s \in S$ an infinite path with label $w_s$, formally we let $T'$ be
the $C$-tree over

$$
V(T') = V(T) \cup (S \times \mathbb{N})
$$
given by

$$E(T') = E(T) \cup \{(s, i) \xrightarrow{w_{s,i}} (s, i+1) \mid s \in S \text{ and } i \in \mathbb{N}\},$$

where it is understood that $(s, 0) = s$ and we write $w_s = w_{s,0}w_{s,1}\dots$. By construction, we get that $\text{val}_{T'}(t_0) = \text{val}^\epsilon_{T^\epsilon}(t_0)$; moreover, $T'$ has cardinality $< \kappa$ (unless $\kappa$ is finite, in which case there is no tree with cardinality $< \kappa$ and the proof is vacuous). There is a morphism $\phi' : T' \to G$ preserving the value at the root by $(\kappa, \text{val})$-universality of $G$.

Finally, we define a map $\phi^\epsilon : T^\epsilon \to G^\epsilon$ by letting $\phi^\epsilon(t) = \phi(t')$, where $t'$ is the unique vertex in $V(T)$ such that $t' \xrightarrow{\epsilon^*} t$ is a path in $T^\epsilon$. It is a direct check that $\phi^\epsilon$ is a morphism, since $G^\epsilon$ includes $\epsilon$-loops around all vertices. $\square$

### 3.4.2. The case of prefix-increasing objectives.
A C-valuation $\text{val}$ is prefix-increasing (resp. prefix-decreasing) if adding a prefix can only increase (resp. decrease) values, meaning that for all $u \in C^*$ and $w \in C^\omega$ we have $\text{val}(uw) \ge \text{val}(w)$ (resp. $\text{val}(uw) \le \text{val}(w)$). We say that $\text{val}$ is prefix-independent if it is both prefix-increasing and prefix-decreasing, that is, for all $u \in C^*$ and $w \in C^\omega$, $\text{val}(uw) = \text{val}(w)$. An objective $W$ is thus prefix-increasing (resp. decreasing, independent) if for all $c \in C$, $cW \supseteq W$ (resp. $\subseteq$, $=$).

Just as in [Ohl23], we may simplify the notions under study when the objective has such properties. First, note that for a prefix-increasing objective $W$ and a tree $T$, it is equivalent that the root of $T$ satisfies $W$, and that $T$ itself (meaning, all vertices in $T$) satisfies $W$.

Now fix a prefix-increasing objective $W \subseteq C^\omega$ and consider a well-monotone graph $U$. Consider moreover the restriction $U'$ of $U$ to vertices which satisfy $W$ (note that $U$ is well-monotone, as is any restriction of a well-monotone graph). Last, let $U^\top$ be the well-monotone graph obtained from $U'$ by appending an additional fresh vertex $\top$, with all possible outgoing edges (and only incoming edges from itself); formally $V(U^\top) = V(U') \cup \{\top\}$ and $E(U^\top) = E(U') \cup \{\top\} \times C \times V(U^\top)$. The following lemma states that the (hypothetical) universality of $U$ transfers to $U^\top$.

**Lemma 3.6** [Ohl23, Lemma 3.9]. Let $\kappa$ be a cardinal. The following conditions are equivalent:

(i) $U$ is $(\kappa, W)$-universal;

(ii) $U^\top$ is $(\kappa, W)$-universal;

(iii) all C-trees of cardinality $< \kappa$ satisfying $W$ have a morphism into $U'$.

Intuitively, the lemma states that in the case of a prefix-increasing objective and when looking for a universal structure, vertices which do not satisfy the objective are irrelevant, and can simply be replaced by $\top$. Observe moreover that antichains are not larger in $U'$ or $U^\top$ than they are in the original graph $U$.

In this way, we can simplify without loss of generality the definition of universality when dealing with prefix-increasing objectives. In the remainder of the paper, if $W$ is a prefix-increasing objective, we will say that a graph $U$ is $(\kappa, W)$-universal for prefix-increasing objectives if:

* $U$ satisfies $W$; and

* it embeds all trees of cardinality $< \kappa$ that satisfy $W$.

When it is clear from the context that $W$ is prefix-increasing, we will just say $(\kappa, W)$-universal.

That is, we may always disregard vertices of universal graphs not satisfying the objective under consideration. We note that the definition of universality that we have just given
coincides with the one introduced (for prefix-independent objectives) by Colcombet and Fijalkow [CF18].

3.4.3. *The case of prefix-independent objectives.* Recall that an objective W is prefix-independent if for all $u \in C^*$ and $w \in C^\omega$,

$$uw \in W \Leftrightarrow w \in W.$$

When dealing with prefix-independent objectives, it is often more natural to consider pretrees, which leads to a stronger definition of universality that may lend itself better to inductive arguments (see for example Sections 4.3 and 6.1). We say that a vertex in a pregraph satisfies an objective if all infinite paths from the vertex satisfy the objective (regardless of finite paths), and that a pregraph satisfies an objective if all its vertices do. This may be unsatisfactory for modelisation purposes, for instance, in the case of a safety condition, since this definition allows for non-safe finite paths; however it poses no issue in the context of prefix-independent objectives for which finite paths are indeed irrelevant.

Given a prefix-independent objective W, we say that a graph U is $(\kappa, W)$-universal for prefix-independent objectives if

* U satisfies W; and

* U embeds all pretrees of cardinality < $\kappa$ that satisfy W.

When it is clear from the context that W is prefix-independent, we will just say that U is $(\kappa, W)$-universal.

We prove that for prefix-independent objectives, this stronger definition of universality can in fact be used without loss of generality. First, we remark that as prefix-independent objectives are a special case of prefix-increasing ones, all remarks from the previous subsection apply.

**Lemma 3.7.** Let $W \subseteq C^\omega$ be a nonempty prefix-independent objective, let U be a C-pregraph and let $\kappa$ be an infinite cardinal. The following are equivalent:

(i) all trees of cardinality < $\kappa$ which satisfy W embed in U;

(ii) all pretrees of cardinality < $\kappa$ which satisfy W embed in U.

*Proof.* The implication (ii) $\implies$ (i) is trivial and therefore we concentrate on the other one. Fix an infinite word $w = w_0w_1\cdots \in W$ and consider a pretree $T'$ of cardinality < $\kappa$ which satisfies W. Let $S \subseteq V(T')$ be the set of sinks in $T'$. Now let $T$ be the tree obtained by appending a path labelled with $w$ to all sinks in $T'$, formally, $V(T) = V(T') \cup (S \times \mathbb{N})$, and

$$E(T) = E(T') \cup \{(s, i) \xrightarrow{w_i} (s, i+1) \mid s \in S \text{ and } i \in \mathbb{N}\};$$

where it is understood that we identify $(s, 0)$ with $s$ for all $s \in S$. Paths in $T$ are either paths in $T'$, or their label end with $w$; thus $T$ satisfies W by prefix-independence. Thus there is a morphism $T \to U$, whose restriction to $V(T')$ is then a morphism $T' \to U$, and the lemma is proved. $\square$
3.4.4. *Almost universality.* In this section, we show how the technically convenient notion of almost universality defined by Ohlmann [Ohl23] adapts to our setting. Recall that $G[v]$ denotes the restriction of $G$ to vertices reachable from $v$.

For a prefix-independent objective $W$, we say that a graph $U$ is almost $(\kappa, W)$-universal if

* $U$ satisfies $W$; and

* all pretrees $T$ satisfying $W$ have a vertex $t$ such that $T[t] \to U$.

The following technical result allows us to build well-monotone universal graphs from almost universal graphs, without any blowup on the size of antichains. Given a well-monotone graph $U$ and an ordinal $\alpha$, we let$^7 U \times \alpha$ be the well-monotone graph given by $V(U \times \alpha) = V(U) \times \alpha$ and

$$E(U \times \alpha) = \{(v, \lambda) \xrightarrow{c} (v', \lambda') \mid \lambda > \lambda' \text{ or } [\lambda = \lambda' \text{ and } v \xrightarrow{c} v' \in E(U)]\};$$

it is illustrated in Figure 8.

<figure><img src="image_13.png" /><figcaption>Figure 8: An illustration of the graph $U \times \alpha$.</figcaption></figure>

**Lemma 3.8.** Let $W$ be a prefix-independent objective, $\kappa$ a cardinal, and assume that $U$ is almost $(\kappa, W)$-universal. Then $U \times \kappa$ is $(\kappa, W)$-universal (for prefix-independent objectives).

The proof is directly adapted from [Ohl23, Lemma 4.5] to this setting.

*Proof.* Consider an infinite path $(u_0, \lambda_0) \xrightarrow{c_0} (u_1, \lambda_1) \xrightarrow{c_1} \dots$ in $U \times \kappa$. Since $\lambda_0 \ge \lambda_1 \ge \dots$, it must be that this sequence is eventually constant by well-foundedness. Therefore, some suffix $u_i \xrightarrow{c_i} u_{i+1} \xrightarrow{c_{i+1}} \dots$ defines a path in some copy of $U$, which implies that $c_i c_{i+1} \cdots \in W$. We conclude by prefix independence that $U \times \kappa$ indeed satisfies $W$.

Let $T$ be a tree of cardinality $\kappa$ which satisfies $W$. We construct by transfinite recursion an ordinal sequence of vertices $\{v_\alpha\}_{\alpha < \lambda_0} \in V(T)$ (for some $\lambda_0 < \kappa$) where for each $\beta < \lambda$, $v_\lambda$ is not reachable from $v_\beta$ in $T$, together with a morphism $\phi_\lambda : T_\lambda \to U$, where $T_\lambda$ is the restriction of $T$ to vertices reachable from $v_\lambda$ but not from $v_\beta$ for $\beta < \lambda$.

Assuming the $v_\beta$'s for $\beta < \lambda$ already constructed (this assumption is vacuous for the base case $\lambda = 0$), there are two cases. If all vertices in $T$ are reachable from some $v_\beta$, then the process stops. Otherwise, we let $T_{\ge \lambda}$ be the restriction of $T$ to vertices not reachable from any $v_\beta$ for $\beta < \lambda$. It is a pretree of cardinality $< \kappa$. By almost $(\kappa, W)$-universality of $U$, there exists some $t \in T_{\ge \lambda}$ such that $T_{\ge \lambda}[t]$ has a morphism towards $U$. We let $v_\lambda = t$ and $\phi_\lambda$ be this morphism.

Since all the $T_\lambda$'s are nonempty, the process must terminate in $\lambda_0$ steps for some ordinal $\lambda_0$ satisfying $\lambda_0 \le |V(T)| < \kappa$. Now observe that any edge in $T$ is either from $T_\beta$ to itself, for some $\beta \le \lambda_0 < \kappa$, or from $T_\beta$ to $T_{\beta'}$ for $\beta' < \beta \le \lambda_0 < \kappa$. This proves that the map $\phi : V(T) \to V(U \times \kappa)$ defined by $\phi(v) = (\phi_\lambda(v), \lambda)$, where $\lambda$ is so that $v \in V(T_\lambda)$, is a morphism from $T$ to $U \times \kappa$. $\square$

<footnote>$^7$Using the vocabulary from Section 6.1, $U \times \alpha$ is the lexicographic product of $U$ and the edgeless pregraph over $\alpha$; this explains the common notation.</footnote>
## 4. EXAMPLES

In this section we show how Theorems 3.1 and 3.2 can provide upper bounds on the memory of different objectives by constructing well-monotone universal graphs. In general, proving tight bounds for the memory of objectives is a hard task, and only the memory of a few classes of objectives has been characterised, notably, for topologically closed objectives [CFH14] and Muller objectives [DJW97].

As a warm-up and to illustrate our tool, we start (Section 4.1) with a few concrete examples. We then turn our focus to topologically closed objectives (Section 4.2) for which we derive a variant of the result of [CFH14]. Finally, we show how the upper bound of [DJW97] for the memory of Muller objectives can be understood in our framework (Section 4.3).

In Table 1, we compile the examples appearing throughout the paper and their exact memory requirements for the different notions of memory that we consider. For an infinite word $w \in C^\omega$ we write $\text{Inf}(w) = \{c \in C \mid w_i = c \text{ for infinitely many } i\}$. For a word $u \in C^*$, we write $\infty(u) = \{w \in C^\omega \mid w \text{ contains infinitely many factors } u\}$ and we let $\text{Fin}(u)$ denote its complement. We let $C^{\ge n} = C^n C^*$.

<table><caption>Table 1: Examples of objectives appearing in the paper and their memory requirements. We also include sizes of minimal parity automata, which give upper bounds to the ε-chromatic memory.</caption><thead><tr><th>Objective</th><th>ε-free memory</th><th>ε-memory</th><th>ε-free chromatic</th><th>ε-chromatic</th><th>Minimal det. parity automaton</th></tr></thead><tbody><tr><td>∞(a) ∩ ∞(b)</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td></tr><tr><td>∀i, w<sub>i</sub> ≠ w<sub>i+1</sub></td><td>2 (Prop. 5.1)</td><td>|C|</td><td>|C|<sup>‡</sup></td><td>|C|<sup>‡</sup></td><td>|C| + 2<sup>†</sup></td></tr><tr><td>(C<sup>*</sup>a)<sup>m</sup> C<sup>≥n</sup> aC<sup>ω</sup></td><td>n + 1</td><td>n + 1</td><td>n + 1</td><td>n + 1</td><td>m + n + 2<sup>†</sup></td></tr><tr><td>∞(bb) ∪ (Fin(b) ∩ Fin(aa))</td><td>2</td><td>2</td><td>2</td><td>2</td><td>3<sup>‡</sup></td></tr><tr><td>|Inf(w)| = 2</td><td>2</td><td>2 [DJW97]</td><td>|C| [Cas22]</td><td>|C| [Cas22]</td><td>|C|(|C| + 1) [Cas22, CCFL24]</td></tr><tr><td>Topologically closed objectives (Section 4.2)</td><td>Unknown</td><td>Width of left quotients [CFH14]</td><td>Unknown</td><td>NP-complete<sup>¶</sup> [BFRV23]</td><td>Left quotients<sup>†</sup></td></tr><tr><td>Muller objective <i>F</i> (Section 4.3)</td><td>Unknown</td><td>mem(<i>F</i>) [DJW97]</td><td>NP-complete<sup>¶</sup> Both notions coincide [Cas22]</td><td></td><td>Leaves of the Zielonka tree [CCFL24]</td></tr></tbody></table>

### 4.1. Concrete objectives.
We start by illustrating the notions presented until now and some methods to derive universality proofs with a few simple concrete examples of objectives.
**Objective** $W_1 = \{w \in \{a,b\}^\omega \mid a \text{ and } b \text{ occur infinitely often in } w\} = \infty(a) \cap \infty(b)$. **Objective** $W_1$ is an example of a Muller objective ($W_1$ = Muller($\{a,b\}$); see Section 4.3 for details). It is known that its $\varepsilon$-memory is exactly 2 [DJW97]. We show, for each cardinal $\kappa$, an $\varepsilon$-separated chromatic and well-monotone ($\kappa, W_1^\varepsilon$)-universal graph of breadth 2. (Since $W_1$ is prefix-independent, we use the corresponding notion of universality, from Section 3.4.3). By Theorem 3.1, this implies that the $\varepsilon$-chromatic memory of $W_1$ is exactly 2.

Fix a cardinal number $\kappa$ and consider the graph $U$ from the left hand side of Figure 9. It is easy to check that $U$ is an $\varepsilon$-separated monotone graph over the set $M = \{a,b\}$ and that it is indeed chromatic and satisfies $W$. We sketch a universality proof; formal details are given for general Muller objectives in Section 4.3.

<figure><img src="image_14.png" /><figcaption>Figure 9: Universal graphs for $W_1$ (on the left) and $W_2$ (on the right, for $C = \{a,b,c\}$). For the graph on the left (as required by the definition of $\varepsilon$-separated graphs), the order coincides with $\xrightarrow{\varepsilon}$; on the right, it is given by $v_0 \ge v_a, v_b, v_c$ and $v_a, v_b, v_c$ incomparable. Edges following from monotonicity are not represented. An edge between boxes indicates that all edges are put between vertices in the respective boxes.</figcaption></figure>

Let $T$ be a $C$-tree of size $< \kappa$ which satisfies $W$, and let $t_0$ be its root. Note that all paths from $t_0$ eventually visit a $b$-edge; there is in fact an ordinal $\lambda_0 < \kappa$ (defined by induction) which counts the maximal amount of $a$-edges seen from $t_0$ before a $b$-edge is seen; we set $\phi(t_0)$ to be $(\lambda_0, \lambda_1)$.

Then for each edge $t_0 \xrightarrow{c} t \in E(T)$ we proceed as follows.

* If $c \in \{a, \varepsilon\}$, we iterate exactly the same process on $t$, but the ordinal count on the number of $a$'s will have decreased (or even strictly decreased if $c = a$) from $t_0$ to $t$, which guarantees that $\phi(t_0) \xrightarrow{a} \phi(t)$ is indeed an edge in $U$.

* If $c = b$, then we iterate the same process of $t$ but inverting the roles of $a$ and $b$; thus $\phi(t)$ is of the form $(b, \lambda_b)$ for some $\lambda_b < \kappa$, and the edge $\phi(t_0) \xrightarrow{b} \phi(t)$ belongs to $U$, as required. This concludes the top-down construction of $\phi$ and the universality proof.

It is not difficult to find lower bounds to see that the $\varepsilon$-free memory of $W_1$ (and therefore all the other notions of memory) is $\ge 2$. For example, a game with just one vertex controlled

<footnote>†Since these objectives are topologically closed or topologically open, they can be recognised by a weak automaton, and the size of a minimal deterministic parity (resp. weak) automaton recognising them is given by the number of left quotients of the objective.</footnote>

<footnote>‡The proof of these claims can be found in Appendix B.</footnote>

<footnote>¶When the objective $W$ is $\omega$-regular (it has a finite number of left quotients) the decision problem is: given a deterministic parity automaton recognising $W$ and $k \in \mathbb{N}$, decide whether the $\varepsilon$-chromatic memory of $W$ is $\le k$.</footnote>
by Eve where she can choose to produce a or b provides this lower bound. Therefore, the exact memory of $W_1$ is 2, for all the different notions of memory.

**Objective** $W_2 = \{w_0w_1w_2\cdots \in C^\omega | \forall i, w_i \neq w_{i+1}\}$. Note that $W_2$ is prefix-increasing, and therefore we use the definition of universality from Section 3.4.2. Consider the graph $U$ with vertices $V(U) = \{v_0\} \cup \{v_c | c \in C\}$ and edges

$$E(U) = \{v \xrightarrow{c} v_c | v \in V(U), c \in C\};$$

see right hand side of Figure 9. With the order with maximal element $v_0$ and otherwise no comparable elements, the graph $U$ is well-monotone of width $|C|$. We prove that it is $W_2$-universal, which implies, by Theorem 3.2, that the $\varepsilon$-memory of $W_2$ is $\leq |C|$. To do so, it suffices to remark that for any tree $T$ satisfying $W$, mapping the root to $v_0$ and every other node $t$ is to $v_c$, where $c$ is the colour of the unique edge towards $t$, defines a morphism.

Proposition 3.5 implies the existence of an $\varepsilon$-separated well-monotone $(\kappa, W_2^\varepsilon)$-universal graph of breadth 2. In fact, an $\varepsilon$-separated graph given by the proof of Proposition 3.5 can be obtained just by adding $\varepsilon$-edges $v_0 \xrightarrow{\varepsilon} v_c$ for $c \in C$ and $\varepsilon$-loops over all vertices. Since the graph obtained in this way is chromatic, we get that the $\varepsilon$-chromatic memory of $W_2$ is also $\leq |C|$. Proposition 5.1 below proves that the $\varepsilon$-memory is exactly $|C|$, and that the $\varepsilon$-free memory is in fact just 2.

**Objective** $W_3 = (C^*a)^m C^{\geq n}a C^\omega$ with $C = \{a, b\}$ and $m, n \geq 1$. We provide a universal graph of width $n+1$ which proves that the $\varepsilon$-memory is $\leq n+1$. A matching lower bound on the $\varepsilon$-free memory follows from the game depicted on Figure 10. We remark that from the minimal automaton for the regular language $L = (C^*a)^m C^{\geq n}a$ we only obtain a straightforward upper bound of $n+m+1$ on the memory.

<figure><img src="image_15.png" /><figcaption>Figure 10: A game where Eve requires memory $n+1$ to ensure objective $W_3$.</figcaption></figure>

Fix a cardinal $\kappa$, and consider the graph $U$ with vertex set

$$V(U) = \{q_0, \dots, q_{m-1}, p_n\} \times \kappa \cup \{p_0, \dots, p_{n-1}\} \cup \{\top\},$$

and edges as in Figure 11.

Let us sketch a proof of universality. Observe that the vertices satisfying $W$ in $U$ are exactly those of the form $(q_0, \lambda)$. Consider a tree $T$ whose root $t_0$ satisfies $W_3$; we aim to build a morphism $T \to U$ mapping $t_0$ to one of the $(q_0, \lambda)$'s. Given a vertex $t \in V(T)$, let $w_t \in C^*$ denote the unique word labelling a path from $t_0$ to $t$.

A vertex $t \in V(T)$ such that $w_t$ has $j < m$ occurrences of $a$ is mapped to a vertex of the form $(q_j, \lambda) \in V(U)$, where $\lambda$ is an ordinal capturing the distance until the next $a$ in $T$. Then a vertex $t \in V(T)$ such that $w_t$ is of the form $w_t = w'au$, where $w'$ has exactly $m-1$ occurrences of $a$ and $|u| = i < n$ is mapped to $p_i$. A vertex $t \in V(T)$ as above with $|u| \geq n$ is mapped to a vertex of the form $(p_n, \lambda)$, where $\lambda$ captures the distance to the next $a$ (which must occur since $t_0$ satisfies $W_3$). Finally, remaining vertices $t \in V(T)$ satisfy
<figure><img src="image_16.png" /><figcaption>Figure 11: The well-monotone graph $U$ which has width $n+1$ and is universal for $W_3$. Edges between boxes represent all possible edges between vertices from these boxes. For readability, second coordinates of vertices are not displayed. The order is as follows: $\top$ is maximal, the $p_i$'s are pairwise incomparable and greater than the $q_j$'s, vertices are ordered within boxes, and the $q_i$'s are ordered. Many edges that follow from monotonicity (for instances, $a$'s pointing down, and edges from $p_i$'s to $q_j$'s) are omitted for clarity.</figcaption></figure>

$w_t \in (C^*a)^m C^{\ge n} a C^*$, and we map them to $\top$. It is easy to verify that the map constructed above indeed defines a morphism.

One may make the graph $U$ $\varepsilon$-separated without blowing up its width (for instance, using Proposition 3.5); however the obtained graph is not chromatic. Nevertheless, with a slightly more involved construction depicted in Figure 12, we obtain a chromatic $\varepsilon$-separated graph of breadth $n+1$, yielding an upper bound of $n+1$ also on the $\varepsilon$-chromatic memory. We omit a proof of universality as it follows roughly the same lines as the one above.

<figure><img src="image_17.png" /><figcaption>Figure 12: An $\varepsilon$-separated chromatic well-monotone graph of breadth $n+1$ which is universal for $W_3$.</figcaption></figure>

**Objective** $W_4 = \infty(bb) \cup (\text{Fin}(b) \cap \text{Fin}(aa))$ **over** $C = \{a, b, c\}$. Note that $W_4$ is prefix-independent. Figure 13 depicts a deterministic parity automaton$^8$ of size 3 recognising $W_4$ (it is shown in Appendix B that there is no smaller automaton for $W_4$); so this yields an upper bound of 3 on the memory of $W_4$. We claim that memory 2 is actually sufficient.
The game depicted on the right witnesses that Eve requires $\varepsilon$-free memory $\ge 2$: positional strategies are losing, but she wins by answering $b$ to $b$ and $a$ to $c$.

<figure><img src="image_18.png" /><figcaption>Figure 13: On the left, a deterministic parity automaton $\mathcal{A}$ with three states recognising $W_4$ (we use max-parity semantics). In the middle, an $\varepsilon$-separated chromatic universal graph $U$ of breadth 2 for $W_4$; as always, edges following from monotonicity are omitted. On the right, a game witnessing that Eve requires $\varepsilon$-free memory $\ge 2$.</figcaption></figure>

Consider the graph $U$ depicted in the middle of Figure 13; formally it is defined over $V(U) = \{q, p, p'\} \times \kappa$ by the order given by two chains, as in the figure, all $\varepsilon$-edges following the order, and all edges of the form

(1.) $(q, \lambda) \xrightarrow{b} (q, \lambda')$;

(2.) $(r, \lambda) \xrightarrow{b} (q, \lambda')$ with $r \in \{p, p'\}$ and $\lambda > \lambda'$;

(3.) $(q, \lambda) \xrightarrow{d} r$ with $d \in \{a, c\}$, $r \in \{p, p'\}$ and $\lambda > \lambda'$;

(4.) $(r, \lambda) \xrightarrow{d} (r', \lambda')$ with $d \in \{a, c\}$, $r, r' \in \{p, p'\}$ and $\lambda > \lambda'$;

(5.) $(r, \lambda) \xrightarrow{c} (r', \lambda)$ with $r, r' \in \{p, p'\}$; and

(6.) $(p', \lambda) \xrightarrow{a} (p, \lambda)$.

Note that $U$ is well-monotone, $\varepsilon$-separated and chromatic and that it has breadth 2.

To prove that $U$ is universal for $W_4$, which implies that $W_4$ has $\varepsilon$-chromatic memory $\le 2$, we proceed as follows. Take a tree $T$ of cardinality $< \kappa$ satisfying $W_4$, and label it top-down by $\rho: V(T) \to \{p, p', q\}$ by following a run in the deterministic automaton $\mathcal{A}$, say, starting from state $q$ (this choice does not matter). Since $T$ satisfies $W$, every branch corresponds to an accepted run, thus on each branch the maximal priority appearing infinitely often is even. To obtain a morphism into $U$, it suffices to append to $\rho(t)$ an ordinal $\lambda \in \kappa$ capturing the number of 1's appearing before the next 2 on paths starting from $t$.

**Objective** $W_5 = \{w \in C^\omega \mid |\text{Inf}(w)| = 2\}$. In [Cas22], Casares uses this Muller objective to provide a separation between chromatic and non-chromatic memory. By the characterisation of the $\varepsilon$-memory of Muller objectives [DJW97] (see also Section 4.3 below), we know that the $\varepsilon$-memory of $W_5$ is exactly 2. However, the size of the alphabet is a lower bound for the $\varepsilon$-free chromatic memory (and therefore, also for the $\varepsilon$-chromatic memory [Cas22]). Figure 14

<footnote n="8">⁸We recall that a *parity automaton* is an automaton over infinite words with transitions labelled by natural numbers called *priorities*. A run in the automaton is accepting if the maximum of the priorities produced infinitely often is even.</footnote>
depicts two universal graphs for $W_5$ which give the two upper bounds ($\varepsilon$-memory 2 and $\varepsilon$-chromatic memory $|C|$).

<figure><img src="image_19.png" /><figcaption>Figure 14: Two well-monotone universal graphs for $W_5$ in the case where $C = \{a, b, c\}$. The one at the top has width 2 and gives the $\varepsilon$-memory upper bound (it coincides with the graph built in Section 4.3) and the one at the bottom is $\varepsilon$-separated and chromatic and gives the bound on the $\varepsilon$-chromatic memory. Many edges which follow from monotonicity (such as the dashed ones) are omitted.</figcaption></figure>

4.2. **Topologically closed objectives.** Let $C$ be a set of colours and $L \subseteq C^*$ be a language of finite words. The safety objective associated to $L$ is defined by

$$ \text{Safe}(L) = \{w \in C^* | w \text{ does not contain any prefix in } L\}. $$

An objective $W$ is topologically closed if $W = \text{Safe}(L)$ for some $L \subseteq C^*$. (This notation is justified since objectives of the form $\text{Safe}(L)$ are exactly the closed subsets of $C^*$ for the Cantor topology.) Colcombet, Fijalkow and Horn [CFH14] characterised the memory<fnref n="9" /> for topologically closed objectives using the notion of left quotient. We show next how to recover a variant of their result by applying Theorem 3.1. It has been recently proven [BFRV23] that given a finite automaton recognising a regular language $L$ and a number $k \in \mathbb{N}$, it is NP-complete to decide whether the $\varepsilon$-chromatic memory of $\text{Safe}(L)$ is $\le k$.

Let $W \subseteq C^*$ be an objective and let $u \in C^*$. We define the *left quotient* of $W$ with respect to $u$ by

$$ u^{-1}W = \{w \in C^* | uw \in W\}. $$

We denote $\text{Res}(W)$ the set of left quotients of $W$, and we consider it ordered by inclusion. We will also write $[u] = u^{-1}W$ for $u \in C^*$, whenever $W$ is clear from the context. We remark that $[u] \subseteq [v]$ implies $[uc] \subseteq [vc]$ for every $c \in C$.

<footnote n="9">⁹Although the authors do not explicitly mention $\varepsilon$-transitions, the lower bound of [CFH14, Lemma 5] makes implicit use of games with $\varepsilon$-transitions.</footnote>
The following result is a version of [CFH14, Theorem 6], but the two statements differ in some slight assumptions<fnref n="10" />.

**Theorem 4.1.** Let $W \subseteq C^\omega$ be a topologically closed objective. Suppose that $(\mathrm{Res}(W), \subseteq)$ is well-founded of width $< \mu$. Then $W$ has $\varepsilon$-free memory $< \mu$. Moreover, if $\mu$ is finite, objective $W$ has $\varepsilon$-memory exactly $\mu$.

**Remark 4.2.** As shown in Section 5.2, if $\mu$ is infinite, we cannot deduce anything about the $\varepsilon$-memory of $W$ by showing $(\kappa, W)$-universal graphs of width $< \mu$ for $W$.

Let $W \subseteq C^\omega$ be a topologically closed objective such that $(\mathrm{Res}(W), \subseteq)$ is well-founded of width $< \mu$. We prove the theorem by giving a construction of a well-monotone $(\kappa, W)$-universal graph of width $< \mu$. Let $(U, \leq)$ be the partially ordered graph given by

* $V(U) = \mathrm{Res}(W) \setminus \{\emptyset\} \cup \{\top\}$ (where $\top$ is a fresh element).

* For $[u], [v] \in \mathrm{Res}(W)$ we define $[u] \leq [v]$ if $[u] \subseteq [v]$. We let $x \leq \top$ for all $x \in V(U)$.

* $[u] \xrightarrow{c} [v] \in E(U)$ for all $[v] \leq [uc]$. Also, $\top \xrightarrow{c} x$ for all $x \in V(U)$ and all $c \in C$.

**Lemma 4.3.** A vertex $[u] \in V(U) \setminus \{\top\}$ satisfies the objective $u^{-1}W$. In particular, vertex $[\varepsilon]$ satisfies $W$.

*Proof.* Let $L \subseteq C^*$ be a language such that $W = \mathrm{Safe}(L)$. Let $w \in C^\omega$ be a word labelling an infinite path from $[v_0] = [u]$ in $U$:

$$[v_0] \xrightarrow{w_0} [v_1] \xrightarrow{w_1} [v_2] \xrightarrow{w_2} \dots$$

We need to show that for any finite prefix $w'$ of $w$, $uw' \notin L$. We remark that this is equivalent to $[uw'] \neq \emptyset$. We prove by induction that $[v_i] \leq [uw_0 \cdots w_{i-1}]$. By definition of $E(U)$, $[v_i] \leq [v_{i-1}w_{i-1}]$. By induction hypothesis $[v_{i-1}] \leq [uw_0 \cdots w_{i-2}]$, so $[v_{i-1}w_{i-1}] \leq [uw_0 \cdots w_{i-2}w_{i-1}]$ and by transitivity, $[v_i] \leq [uw_0 \cdots w_{i-1}]$. Therefore, for any finite prefix $w' = w_0 \dots w_{k-1}$ it holds that $\emptyset < [v_k] \leq [uw_0 \dots w_{k-1}]$, which concludes the proof. $\square$

**Proposition 4.4.** For all cardinals $\kappa$, $(U, \leq)$ is a well-monotone $(\kappa, W)$-universal graph of width $< |\mu|$.

*Proof.* By the hypothesis of well-foundedness and on the size of the antichains of $\mathrm{Res}(W)$, graph $(U, \leq)$ is well-founded and has width $< |\mu|$.

For the monotonicity, suppose that $x \geq y \xrightarrow{c} y' \geq x'$. If $x = \top$, then $x \xrightarrow{c} x'$ by definition. If not, $x = [u]$, $y = [v]$, $y' = [v']$ and $x' = [u']$ for some words $u, v, v', u'$. By definition of $E(U)$, $[v'] \leq [vc]$. Since $[v] \leq [u]$ implies $[vc] \leq [uc]$, we deduce by transitivity that $[u'] \leq [uc]$ and therefore $u \xrightarrow{c} u'$.

Finally, we prove the $(\kappa, W)$-universality of $(U, \leq)$. Let $T$ be a $C$-tree with root $t_0$. If $t_0$ does not satisfy $W$, the map $\phi(t) = \top$ for all $t \in V(T)$ is a morphism that preserves the value at $t_0$. If $t_0$ satisfies $W$, we define a morphism $\phi : T \to U$ satisfying that $\phi(T) \subseteq \mathrm{Res}(W) \setminus \{\emptyset\}$ in a top-down fashion: $\phi(t) = [u]$, for $u \in C^*$ the unique word labelling a path from $t_0$ to $t$ in $T$. In particular, $\phi(t_0) = [\varepsilon]$, so by Lemma 4.3 $\phi$ preserves the value at $t_0$. Finally, we verify that $\phi$ is a morphism: let $t \xrightarrow{c} t'$ be an edge in $T$. If $u$ is the word labelling the path from $t_0$ to $t$, the word labelling the path from $t_0$ to $t'$ is $uc$, so $\phi(t) = [u]$ and $\phi(t') = [uc]$. By definition, $[u] \xrightarrow{c} [uc] \in E(U)$, so $\phi$ is a morphism. $\square$

<footnote n="10">¹⁰In [CFH14], authors only consider finite branching graphs and objectives over finite alphabets. Nonetheless, they do not need to suppose that $\mathrm{Res}(W)$ is well-founded. In this respect, the two results are incomparable.</footnote>
4.3. **Muller objectives.** Recall that for an infinite word $w \in C^\omega$ we let $\text{Inf}(w) = \{c \in C \mid w_i = c \text{ for infinitely many } i\}$. A *Muller objective* over a finite set of colours $C$ is given by a family $\mathcal{F} \subseteq \mathcal{P}^{\neq \emptyset}(C)$ of non-empty subsets of $C$ and defined by

$$ \text{Muller}(\mathcal{F}) = \{w \in C^\omega \mid \text{Inf}(w) \in \mathcal{F}\}. $$

By a slight abuse, we will say that $\mathcal{F}$ is a Muller objective over $C$.

The exact $\varepsilon$-memory for Muller objectives was characterised by Dziembowski, Jurdziński and Walukiewicz [DJW97] using the notion of Zielonka trees, introduced by Zielonka to study the positionality of Muller objectives [Zie98]. It has been recently shown that the $\varepsilon$-memory of a Muller objectives also coincides with the minimal size of a good-for-games$^{11}$ Rabin automaton recognising it [CCL22]. Concerning their $\varepsilon$-free and chromatic memory, Casares showed [Cas22] that (1) there are Muller objectives whose $\varepsilon$-free memory is strictly smaller than its $\varepsilon$-memory, (2) for all Muller objectives the exact $\varepsilon$-chromatic memory and the exact $\varepsilon$-free chromatic memory coincide and (3) deciding if the chromatic memory of a Muller objective is $\leq k$ is NP-complete.

In this section we will focus on the study of the $\varepsilon$-memory, and we will show how to recover the upper bound presented in [DJW97] by means of well-monotone universal graphs. We now present the necessary definitions to recall their characterisation.

We say that a Muller objective $\mathcal{F} \subseteq \mathcal{P}^{\neq \emptyset}(C)$ over $C$ is *positive* if $C \in \mathcal{F}$, and that it is *negative* otherwise. Given a subset $C' \subseteq C$ of colours, we define the *restriction* $\mathcal{F}|_{C'}$ of $\mathcal{F}$ to $C'$ to be the Muller objective over $C'$ given by

$$ \mathcal{F}|_{C'} = \{F \in \mathcal{F} \mid F \subseteq C'\}. $$

The *children* of a positive (resp. negative) Muller objective $\mathcal{F}$ are the restrictions $\mathcal{F}|_{C'}$ of $\mathcal{F}$ to maximal subsets $C' \subseteq C$ of colours such that $C' \notin \mathcal{F}$ (resp. $C' \in \mathcal{F}$). Muller objectives with no children are called *basic*, they are exactly those of the form $\mathcal{F} = \emptyset$ or $\mathcal{F} = \mathcal{P}(C)$ over $C$.

Note that children of a non-basic positive Muller objective are negative and vice-versa, and that they are defined over strictly smaller sets of colours. Observe finally that a Muller objective defined over a singleton set of colours is necessarily basic. The $\varepsilon$-memory of a Muller objective can be computed bottom-up from its *Zielonka tree*: a structure displaying the parenthood relation for the children of the condition and all its descendants (defined recursively). Proposition 4.5 details this computation. For a formal exposition of the Zielonka tree and its uses, see [DJW97, Hor08, CCL22].

**Proposition 4.5** [DJW97]. Let $\mathcal{F}$ be a Muller objective. The exact $\varepsilon$-memory of Muller($\mathcal{F}$) is given by

$$ \text{mem}(\mathcal{F}) = \begin{cases} 1 & \text{if } \mathcal{F} \text{ is basic,} \\ \sum_{\mathcal{F}' \text{ child of } \mathcal{F}} \text{mem}(\mathcal{F}') & \text{if } \mathcal{F} \text{ is positive non-basic,} \\ \max_{\mathcal{F}' \text{ child of } \mathcal{F}} \text{mem}(\mathcal{F}') & \text{if } \mathcal{F} \text{ is negative non-basic.} \end{cases} $$

**Remark 4.6.** As remarked by Casares [Cas22], this characterisation no longer holds for $\varepsilon$-free memories or chromatic ones.

<footnote>$^{11}$A good-for-games automaton is a non-deterministic automaton for which the non-determinism can be resolved based on the input processed so far.</footnote>
As an example, let $C = \{a, b, c\}$ and consider the Muller objective given by

$$ \mathcal{F} = \{\{a, b\}, \{a, c\}, \{b\}\}. $$

In Figure 15 we show the set of colours of the descendants of $\mathcal{F}$ arranged in a Zielonka tree. For this objective, $\text{mem}(\mathcal{F}) = 2$.

<figure><img src="image_20.png" /><figcaption>Figure 15: Zielonka tree for $\mathcal{F} = \{\{a, b\}, \{a, c\}, \{b\}\}$. A subtree rooted at a circle (resp. square) node labelled $C'$ corresponds to a positive (resp. negative) Muller objective over $C'$.</figcaption></figure>

The remainder of this section is devoted to obtaining a construction of a well-monotone $(\kappa, \text{Muller}(\mathcal{F}))$-universal graph of width $\le \text{mem}(\mathcal{F})$ for a Muller objective $\mathcal{F}$ over a finite set of colours $C$ and a cardinal $\kappa$. As always for prefix-independent objectives (see Section 3.4.3), recall that being $\kappa$-universal means satisfying the objective, and embedding all $C$-pretrees of cardinality $< \kappa$ whose infinite branches satisfy the objective.

We start with positive and negative basic objectives, which are dealt with separately.

**If $\mathcal{F}$ is positive basic, $\mathcal{F} = \mathcal{P}(C)$:** In this case, the objective is trivially winning: $\text{Muller}(\mathcal{F}) = C^\omega$. It is easy to see that the graph consisting in just one vertex with a self loop for each colour in $C$ is well-monotone $(\kappa, \text{Muller}(\mathcal{F}))$-universal and of width 1, as required.

**If $\mathcal{F}$ is negative basic, $\mathcal{F} = \emptyset$:** In this case, the objective is trivially losing: $\text{Muller}(\mathcal{F}) = \emptyset$. Let us define $U$ over $V(U) = \kappa$ by

$$ x \stackrel{c}{\to} y \in E(U) \iff x > y; $$

it is a well-monotone pregraph with width 1. Note that graphs satisfying $\text{Muller}(\mathcal{F})$ are exactly those without infinite paths, which is the case of $U$. Now any $C$-pretree $T$ of cardinality $< \kappa$ without infinite branches can be embedded in $U$ by a morphism $\phi$ defined in a bottom-up fashion: if $t \in V(T)$ is a sink then $\phi(t) = 0$, and otherwise $\phi(t) = \sup\{\phi(t') | t \stackrel{c}{\to} t' \in E(T)\}$.

We now assume that $\mathcal{F}$ is non-basic, with children $\mathcal{F}_1, \dots, \mathcal{F}_s$ respectively over $C_1, \dots, C_s \subsetneq C$. For each $i$, we obtain by induction a well-monotone $(\kappa, \text{Muller}(\mathcal{F}_i))$-universal graph $U_i$ with width $\le \text{mem}(\mathcal{F}_i)$. For convenience, we assume that the $V(U_i)$'s are pairwise disjoint.

**If $\mathcal{F}$ is positive non-basic:** We define the desired graph $(U, \le)$ by putting the $U_i$ parallel to each other, and adding edges in between in a cycling fashion. See the left-hand side of Figure 16.
<figure><img src="image_21.png" /><figcaption>Figure 16: On the left, the construction for positive Muller objectives (putting $U_i$'s in parallel); on the right, the construction for negative Muller objectives (putting $U_i$'s in series).</figcaption></figure>

Formally, we put $V(U) = \bigcup_{i=1}^{s} V(U_i)$, and set

$$E(U) = \bigcup_{i=1}^{s} E(U_i) \cup \bigcup_{i=1}^{s} \{v \xrightarrow{c} v' \mid v \in V_i, v' \in V_{i+1} \text{ and } c \notin C_i\}.$$

where it is understood that $s + 1$ is identified with 1. The partial order on $U$ is given by

$$v \geq v' \text{ in } U \iff \exists i, [v, v' \in V(U_i) \text{ and } v \geq v' \text{ in } U_i].$$

There remains to prove the following claim.

**Claim 4.7.** Graph $(U, \leq)$ is well-monotone, $(\kappa, \text{Muller}(\mathcal{F}))$-universal and has width $\leq \text{mem}(\mathcal{F}) = \sum_{i=1}^{s} \text{mem}\mathcal{F}_i$.

*Proof of the claim.* Well-monotonicity of $U$ follows directly from well-monotonicity of the $U_i$'s. The bound its width $U$ is also direct.

We now prove that $U$ is $(\kappa, \text{Muller}(\mathcal{F}))$-universal. First, we show that $U$ satisfies $\text{Muller}(\mathcal{F})$. Infinite paths that eventually remain in some $U_i$ satisfy $\text{Muller}(\mathcal{F}_i) \subseteq \text{Muller}(\mathcal{F})$. Colour sequences $w \in C^\omega$ of other infinite paths have infinitely many occurrences of colours not in $C_i$, for each $i$, and therefore $\text{Inf}(w)$ is not a subset of any of the $C_i$'s: it has to belong to $\mathcal{F}$ by maximality of the $C_i$'s.

We now let $T$ be a pretree of cardinality $< \kappa$ with root $t_0$ satisfying $\text{Muller}(\mathcal{F})$. Let us first label vertices of $T$ by integers from $\{1, \dots, s\}$ in a top-down fashion; these labels $\ell: V(T) \to \{1, \dots, s\}$ will determine in which $U_i$ will the vertices be mapped, and are defined as follows:

* we set $\ell(t_0) = 1$, and

* for each $t \xrightarrow{c} t' \in E(T)$, assuming $\ell(t)$ is defined, if $c \in C_{\ell(t)}$ we let $\ell(t') = \ell(t)$ and otherwise we let $\ell(t') = \ell(t) + 1$ (or 1 if $\ell(t) = s$).

For each $i$, we let $G_i$ be the pregraph obtained as the restriction of $T$ to $\ell^{-1}(i)$.
Observe that $G_i$ is a $C_i$-pregraph satisfying Muller($\mathcal{F}$), and therefore it satisfies Muller($\mathcal{F}_i$) since $\mathcal{F}_i$ is the restriction $\mathcal{F}|_{C_i}$ of $\mathcal{F}$ to $C_i$. Moreover, $G_i$ is a disjoint union of pretrees (as a restriction of a pretree), each of which is of cardinality $< \kappa$. Thus by induction we define, for each $i$, a morphism $\phi_i: G_i \to U_i$.

Observe finally that each edge in $E(T)$ either belongs to $E(G_i)$ for some $i$, or is of the form $v \xrightarrow{c} v'$ with $\ell(v) = i$, $\ell(v') = i+1$ (or $1$ if $i = s$) and $c \notin C_i$. This precisely ensures that the sum of the $\phi_i$'s defines a morphism $T \to U$, as required. $\triangleleft$

**If $\mathcal{F}$ is negative non-basic:** We will in this case construct an almost universal graph well-monotone graph $U$ and conclude thanks to Lemma 3.8; it is defined by putting the $U_i$'s in series (see right-hand side of Figure 16). Formally, we let $U$ be given by $V(U) = \sum_{i=1}^s V(U_i)$, ordered by

$$v \ge v' \text{ in } U \iff i > i' \text{ or } [i = i' \text{ and } v \ge v' \text{ in } U_i],$$

where $v \in V(U_i)$ and $v' \in V(U_{i'})$, and with edges given by

$$E(U) = \sum_{i=1}^{s} E(U_i) \cup \{v \xrightarrow{c} v' \mid v \in V(U_i) \text{ and } v' \in V(U_{i'}) \text{ with } i > i'\}.$$

We now concentrate on the following claim which, together with Lemma 3.8, implies that $U \times \kappa$ is $(\kappa, \text{Muller}(\mathcal{F}))$-universal, which concludes the proof.

**Claim 4.8.** The well-monotone graph $U$ is almost $(\kappa, \text{Muller}(\mathcal{F}))$-universal and has antichains bounded by $\text{mem}(\mathcal{F}) = \max_i \text{mem}(\mathcal{F}_i)$.

*Proof of the claim.* Well-monotonicity as well as the bound on the width are both a direct proof; we focus on almost universality. First, observe that an infinite path in $U$ eventually remains in some $U_i$ and therefore satisfies Muller($\mathcal{F}_i$) $\subseteq$ Muller($\mathcal{F}$).

We now let $T$ be a $C$-pretree of cardinality $< \kappa$ which satisfies Muller($\mathcal{F}$), and aim to show that there is a vertex $t \in V(T)$ such that $T[t]$, embeds in some $U_i$ (and thus, by composition with the inclusion morphism, in $U$). Since such $T[t]$'s are pretrees of cardinality $< \kappa$ satisfying Muller($\mathcal{F}$), it suffices by induction that for some $t$ and some $i$, all colours appearing in $T[t]$ belong to $C_i$.

Towards a contradiction, assume otherwise. Then we will construct an infinite path

$$\pi = t_0 \xrightarrow{w_0} t'_0 \xrightarrow{c_1} t_1 \xrightarrow{w_1} t'_1 \xrightarrow{c_2} \dots$$

in $T$ as follows. Assume $\pi$ constructed up to $t_j$ with $j = ks + i$. Since $T[t_j]$ contains an edge colour $c_{j+1} \notin C_j$, we let $t'_j \xrightarrow{c_j} t_{j+1}$ be such an edge, and extend $\pi$ with the path $t_j \xrightarrow{w_j} t'_j$ followed by the above edge. Since there are finitely many colours this implies that $\text{Inf}(w)$ is not a subset of any of the $C_i$'s, and therefore $\pi$ does not satisfy Muller($\mathcal{F}$), the wanted contradiction. $\triangleleft$

Figure 17 depicts the universal graph obtained using this construction for the Muller condition from Figure 15.

Objective $W_1$ from Section 4.1 is another simpler example of a Muller objective. The graph shown in Figure 9 coincides with the one obtained by following the above procedure.

Thanks to Proposition 3.5 and Theorem 3.1, we conclude with the upper bound in Proposition 4.5; for the lower bound we refer to [DJW97].
<figure><img src="image_22.png" /><figcaption>Figure 17: The universal graph obtained for the Muller objective given by $\mathcal{F} = \{{\{a, b\}}, \{a, c\}, \{b\}\}$ (the corresponding Zielonka tree is given in Figure 15).</figcaption></figure>

## 5. COUNTEREXAMPLES

A few counterexamples which set the limits of our approach are given in this section.

**5.1. No structuration theorem for $\varepsilon$-free memory.** In this section, we show that the converse of Theorem 3.2 does not hold, even in the case of objectives. The counterexample we provide is a generalisation to infinite cardinals of the example proposed by Casares [Cas22] for showing that the $\varepsilon$-memory can be strictly smaller than the $\varepsilon$-free one.

**Proposition 5.1.** For each cardinal $\mu$ there is a set of colours $C_\mu$ and an objective $W_\mu \subseteq C_\mu^\omega$ satisfying:

(1) The $\varepsilon$-free memory of $W_\mu$ is $\le 2$.

(2) The $\varepsilon$-free memory of $W_\mu^\varepsilon$ is $\ge \mu$; and therefore the $\varepsilon$-memory of $W_\mu$ is $\ge \mu$.

(3) There is $\kappa$ such that any monotone $(\kappa, W_\mu)$-universal graph has width $\ge \mu$.

Note that combining the two first items with Proposition 3.5, we already obtain that the converse of Theorem 3.2 fails. We include the third item, as it slightly strengthens this result, and we provide a direct proof of it.

*Proof of Proposition 5.1.* Let $C_\mu = \mu$ and $W_\mu = \{w_0w_1\cdots \in C_\mu^\omega \mid \forall i, w_i \ne w_{i+1}\}$.<fnref n="12" />

(1) We first prove that the $\varepsilon$-free memory of $W_\mu$ is $\le 2$. Let $\mathcal{G} = (G, V_{\text{Eve}}, v_0, W_\mu)$ be a game that is won by Eve. Since $W_\mu$ is prefix-increasing, we can assume without loss of generality that for all $v \in V(G)$, Eve wins the game $\mathcal{G}_v = (G, V_{\text{Eve}}, v, W_\mu)$. Therefore we may assume that for each $v \xrightarrow{c} v' \in E(G)$, if $v' \in V_{\text{Eve}}$, $v'$ has an outgoing edge not labelled by $c$, and if $v' \in V_{\text{Adam}}$ then $v'$ has no outgoing edge labelled with $c$.

We define a strategy implementing the following idea: for each vertex $v \in V_{\text{Eve}}$, Eve fixes two outgoing edges labelled by $c_{v,1} \ne c_{v,2}$ (if possible). When she has to play from $v$, the strategy just remembers if the colour produced in the preceding action was $c_{v,1}$ (in which case she chooses to play $c_{v,2}$) or not (in which case she can play $c_{v,1}$ safely).

We define this strategy formally. For each $v \in V_{\text{Eve}}$, if $v$ has at least two outgoing edges labelled with two different colours, we choose two of them: $v \xrightarrow{c_{v,1}} v'_1$, $v \xrightarrow{c_{v,2}} v'_2$, $c_{v,1} \ne c_{v,2}$ (if the same colour labels all outgoing edges of $v$, we take $c_{v,1} = c_{v,2}$, $v'_1 = v'_2$). For $v \in V_{\text{Adam}}$, we let $c_{v,1}$ be a fresh colour not in $C_\mu$ (so that it is different from all $c \in C_\mu$ in the conditions below). We define $S = (S, \pi_S, s_0)$ as follows:

* $V(S) = V(G) \times \{1\} \sqcup V_{\text{Eve}} \times \{2\}$.

* $s_0 = (v_0, 1)$.

<footnote n="12">¹²Condition $W'_\mu = \{w \in C_\mu^\omega \mid \nexists c \in C_\mu, \nexists u \in C_\mu^* \text{ such that } w = uc^\omega\}$ also verifies the desired property.</footnote>
* If $v \in V_{\text{Adam}}$ and $v \xrightarrow{c} v' \in E(G)$, if $c \neq c_{v',1}$, $(v, 1) \xrightarrow{c} (v', 1) \in E(S)$. If $c = c_{v',1}$, $(v, 1) \xrightarrow{c} (v', 2) \in E(S)$.

* For $v \in V_{\text{Eve}}$ and $i \in \{1, 2\}$, if $c_{v,i} \neq c_{v',1}$ we let $(v, i) \xrightarrow{c_{v,i}} (v', 1) \in E(S)$. If $c_{v,i} = c_{v',1}$ we let $(v, i) \xrightarrow{c_{v,i}} (v', 2) \in V(S)$.

* $\pi_S(v, i) = v$.

As we have supposed that after visiting a c-edge Eve have some option not labelled with c, the above strategy only contains paths satisfying $W_\mu$.

(2) We now prove that the memory of $W_\mu^\varepsilon$ is$^{13} \ge \mu$. Consider the game $\mathcal{G} = (G, V_{\text{Eve}}, v_0, W_\mu)$ over $V(G) = \{v_0\} \sqcup \mu$, where $v_0 \notin \mu$ is a fresh element, by $V_{\text{Eve}} = \{v_0\}$ and

$$E(G) = \{v_0 \xrightarrow{\varepsilon} x \mid x \in \mu\} \cup \{x \xrightarrow{y} v_0 \mid y \neq x\}.$$

Eve wins this game using the following strategy: whenever Adam picks an edge $x \xrightarrow{y} v_0$, she sends him to vertex $y$ (from where he cannot pick colour $y$ again). The game $\mathcal{G}$ is depicted in Figure 18.

<figure><img src="image_23.png" /><figcaption>Figure 18: The game $\mathcal{G}$ in the proof on the second item of Proposition 5.1.</figcaption></figure>

In this way, the produced sequence does not contain two consecutive colours that are equal, thus Eve wins.

Let $S = (S, \pi_S, s_0)$ be an strategy such that $|\pi_S^{-1}(v_0)| < \mu$. We will show that $S$ is not winning. For each $s \in \pi_S^{-1}(v_0)$, choose $x_s \in V(S)$ such that $s \xrightarrow{\varepsilon} x_s \in E(S)$. Let $y \in \mu \setminus \{\pi_S(x_s) \mid s \in \pi_S^{-1}(v_0)\}$ be the image under $\pi_S$ of an element which is never chosen (which exists since $|\pi_S^{-1}(v_0)| < \mu$). The strategy $S$ contains the following losing path:

$$s_0 \xrightarrow{\varepsilon} x_{s_0} \xrightarrow{y} s_1 \xrightarrow{\varepsilon} x_{s_1} \xrightarrow{y} s_2 \xrightarrow{\varepsilon} x_{s_2} \xrightarrow{y} s_3 \dots$$

(3) Let $\kappa = \max\{\aleph_0, \mu\}$. We define a $C_\mu$-tree $T$ of cardinality $\kappa$ that cannot be embedded in any monotone $C_\mu$-graph with width $< \mu$ by a morphism $\phi$ that preserves the value at the root $t_0$. We define $T$ over

$$V(T) = \{w_0 \dots w_k \in \mu^* \mid w_i \neq w_{i+1} \text{ for all } 0 \le i < k\},$$

by

$$E(T) = \{w_0 \dots w_k \xrightarrow{c} w_0 \dots w_k c \mid c \in \mu \setminus \{w_k\}\},$$

with root $t_0 = \varepsilon$. In words, $T$ consists of finite sequences of elements in $\mu$ whose pairwise consecutive elements differ, and the successors of a vertex $t \in V(T)$ are those obtained by adding a colour different from the one in the last position. By construction, all paths from $t_0$ satisfy $W_\mu$. Moreover, since $\kappa$ is infinite it holds that $|T| = \kappa$ as claimed.

<footnote n="13">¹³In fact, if $\mu$ is infinite we will prove that the memory of $W_\mu$ is $> \mu$.</footnote>
Let $(G, \leq)$ be a monotone $C$-graph with antichains of cardinality $< \mu$ and let $\phi: T \to G$ be a morphism. We show that $\phi(t_0)$ does not satisfy $W_\mu$ in $G$. Consider the set of vertices at the first level of the tree, that is, $V_1 = \{t \in V(T) | t \in \mu\}$. As any antichain of $G$ has cardinality $< \mu$, there are two different elements $t, t' \in V_1 \subseteq \mu$ such that $\phi(t)$ and $\phi(t')$ are comparable; we assume without loss of generality that $\phi(t') \leq \phi(t)$. Observe that $t \xrightarrow{t'} tt' \in E(T)$, and therefore $\phi(t) \xrightarrow{t'} \phiCCI(tt') \in E(G)$ since $\phi$ is a morphism. By monotonicity it follows that $\phi(t') \xrightarrow{t'} \phiCCI(tt') \in E(G)$. We deduce that $G$ contains a path from $\phi(t_0)$ starting by

$$ \phi(t_0) \xrightarrow{t'} \phi(t') \xrightarrow{t'} \phiCCI(tt') \dots, $$

and thus $\phi(t_0)$ does not satisfy $W_\mu$.

<figure><img src="image_24.png" /></figure>

**5.2. Universal graphs with antichains of unbounded size do not determine the $\varepsilon$-memory.** As observed by Perles [Per63], Dilworth's Theorem (c.f. Theorem A.2) does not hold if the upper bound on the width is infinite. More precisely, he proved that for any cardinal $\kappa$, all antichains of the coordinate-wise order $\kappa \times \kappa$ are finite, but it cannot be decomposed in less than $\kappa$ disjoint chains.

In this section we show that Proposition 3.5 does not hold if the bound on the size of the antichains of the graph is not finite: the existence of a well-monotone $(\kappa, \text{val})$-universal graph of width $< \mu$ does not provide any information on the $\varepsilon$-memory of $\text{val}^\varepsilon$ if $\mu$ is infinite (even if $\text{val}$ is an objective).

**Proposition 5.2.** For any infinite cardinal $\mu$, there exists an objective $W_\mu$ such that

* for all cardinals $\kappa$ there exists a well-monotone $(\kappa, W_\mu)$-universal graph whose antichains have cardinality $< \aleph_0$; and

* there is an $\varepsilon$-game with objective $W_\mu^\varepsilon$ in which Eve cannot reach the value with $\varepsilon$-memory $< \mu$.

The rest of this section is devoted to the proof of Proposition 5.2. Fix an infinite cardinal $\mu$. Let $C_\mu = \mu \times \mu$ and let $W_\mu$ be the objective:

$$ W_\mu = \{(w, w') \in C_\mu^\omega \mid \exists i \text{ such that } w_i < w_{i+1} \text{ and } w'_i < w'_{i+1}\}. $$

In words, Eve wins as long as at each step, one of the two coordinates does not increase. Clearly, objective $W_\mu$ is topologically closed, therefore thanks to Proposition 4.4, it suffices to study its left quotients in order to construct well-monotone universal graph. We now prove that the left quotients of $W_\mu$ form a well-quasi order.

**Lemma 5.3.** The partial order $(\text{Res}(W_\mu), \subseteq)$ is a well-quasi order (wqo).

*Proof.* We will prove that $(\text{Res}(W_\mu) \setminus \{\emptyset\}, \subseteq)$ is order-isomorphic to $(\mu \times \mu, \leq)$ ordered coordinatewise:

$$ (x, y) \leq (x', y') \iff x \leq x' \text{ and } y \leq y', $$

which is well-known to be a wqo.

First, observe that for $(u, v) = (u_0 \dots u_n, v_0 \dots v_n) \in C_\mu^*$ such that $(u, v)^{-1}W_\mu \neq \emptyset$, it holds that $(u, v)^{-1}W_\mu = (u_n, v_n)^{-1}W_\mu$ (that is, the last letters determine the left quotient). We aim to prove that for all $(x, y), (x', y') \in \mu \times \mu$ it holds that

$$ (x, y) \leq (x', y') \iff (x, y)^{-1}W_\mu \subseteq (x', y')^{-1}W_\mu. $$
If $(x, y) \le (x', y')$, then for any $(w, w') = (w_0w_1\dots, w'_0w'_1\dots) \in C_\mu^\omega$, if $(xw, yw') \in W_\mu$, then in particular $x \ge w_0$ or $y \ge w'_0$; and there is not $i \in \omega$ such that $w_i < w_{i+1}$ and $w'_i < w'_{i+1}$. Therefore, $x' \ge w_0$ or $y' \ge w'_0$ and $(x'w, y'w') \in W_\mu$. Conversely, if $(x, y) \not\le (x', y')$, we suppose without loss of generality that $x > x'$. Then $((x' + 1)^\omega, y^\omega) \in (x, y)^{-1}W_\mu$ but $((x' + 1)^\omega, y^\omega) \notin (x', y')^{-1}W_\mu$. $\square$

Applying Proposition 4.4 then yields the first item in Proposition 5.2.

We now define an $\varepsilon$-game won by Eve, but in which she needs to use an $\varepsilon$-strategy with memory at least $\mu$; we start with a formal definition, the intuition is explained below. We write $\mathcal{P}^{=2}(\mu \times \mu)$ to denote the set of subsets of $\mu \times \mu$ of size 2. For $(x, y) \in \mu \times \mu$ we write $(x, y)^> = \{(x', y') \in \mu \times \mu \mid (x, y) < (x', y')\}$.

Let $G_\mu = (G, V_{Eve}, v_0, W_\mu^\varepsilon)$ be the game defined as follows.

* $V(G) = \{v_0\} \cup \mu \times \mu \cup \mathcal{P}^{=2}(\mu \times \mu)$.

* $V_{Eve} = \mathcal{P}^{=2}(\mu \times \mu)$.

* $E(G)$ contains the following edges:

- $v_0 \xrightarrow{(x,y)} (x,y)$ for all $(x,y) \in \mu \times \mu$.

- For $(x,y) \in \mu \times \mu$, $(x,y) \xrightarrow{\varepsilon} A$ for all $A \in \mathcal{P}^{=2}(\mu \times \mu)$ such that $A \not\subseteq (x,y)^>$.

- For $A \in \mathcal{P}^{=2}(\mu \times \mu)$, $A \xrightarrow{(x,y)} (x,y)$ for $(x,y) \in A$.

That is, in the game Adam and Eve alternate moves as follows: Eve picks an element $(x, y) \in \mu \times \mu$ amongst two options (the two elements in some set $A$) and then Adam can choose what are going to be the options in Eve's next move, as long as she has at least one non-losing move. The first move is done by Adam, he can choose the first element of the sequence. Note the similarity with the gadget from the proof of Section 3.3.

In the game $G_\mu$, Eve has a strategy ensuring that a path satisfying $W_\mu^\varepsilon$ will be produced: whenever Adam sends her to a vertex $A \in \mathcal{P}^{=2}(\mu \times \mu)$, she can choose an element that “keeps her alive” (she does not produce an increasing pair). We are now ready to prove the second item in Proposition 5.2.

**Lemma 5.4.** In the game $G_\mu = (G, V_{Eve}, v_0, W_\mu^\varepsilon)$ Eve cannot win using an $\varepsilon$-strategy with memory $< \mu$.

*Proof.* Let $S = (S, \pi_S, s_0)$ be an $\varepsilon$-strategy over a set $M$ such that $|\pi_S^{-1}(v)| < \mu$ for every $v \in V(G)$. We will prove that $S$ contains a losing path from $s_0 = (v_0, m_0)$.

For each $q \in \mu \times \mu$ we pick $m_q \in M$ such that $(v_0, m_0) \xrightarrow{q} (q, m_q) \in E(S)$, and we let $M' = \{m_q \in M \mid q \in \mu \times \mu\}$. We let $p_1 = (1, 0)$ and $p_2 = (0, 1)$. Observe that for any $q \in \mu \times \mu$, $q \xrightarrow{\varepsilon} \{p_1, p_2\} \in E(G)$, and therefore for any $q \in \mu \times \mu$, since $S$ is an $\varepsilon$-strategy, $q \in V_{Adam}$, $q \xrightarrow{\varepsilon} \{p_1, p_2\} \in E(G)$ and $(q, m_q) \in V(S)$, it holds that $(q, m_q) \xrightarrow{\varepsilon} (\{p_1, p_2\}, m_q) \in E(S)$. Thus there is a different element for each $m_q$ in the fiber above $\{p_1, p_2\}$, and we deduce that $|M'| < \mu$, and we can find two different elements $q_1, q_2 \in \mu \times \mu$ such that $m_{q_1} = m_{q_2} = m$. Moreover, since $\mu \times \mu$ cannot be decomposed in less than $\mu$ disjoint chains [Per63], we can pick $q_1$ and $q_2$ incomparable. Pick $t_1, t_2 \in \mu \times \mu$ satisfying

* $q_1 \prec t_1, q_2 < t_1$,

* $q_2 \prec t_2, q_1 < t_2$.

Therefore, when Adam plays $\{t_1, t_2\}$ from $q_1$, Eve should play $t_1$, and when Adam plays it from $q_2$ she should choose $t_2$. However, the strategy $S$ contains the edge $(\{t_1, t_2\}, m) \xrightarrow{t'} t'$,
for both $t' \in \{t_1, t_2\}$, and therefore $\mathcal{S}$ contains infinite paths starting by the following two possibilities

$$ (v_0, m_0) \xrightarrow{q_1} (q_1, m) \xrightarrow{\epsilon} (\{t_1, t_2\}, m) \xrightarrow{t'} (t', m'), $$

$$ (v_0, m_0) \xrightarrow{q_2} (q_2, m) \xrightarrow{\epsilon} (\{t_1, t_2\}, m) \xrightarrow{t'} (t', m'), $$

one of which violates the objective $W_{\mu}^{\epsilon}$.

<figure><img src="image_25.png" /></figure>

**5.3. Universal graphs need to embed just trees, not graphs.** There is a discrepancy between the notions of universality used in Ohlmann's characterisation of positionality [Ohl23] (which comes from the work of Colcombet and Fijalkow [CF19]) and the one introduced in this paper: in Ohlmann's paper [Ohl23], for a graph $U$ to be universal it must embed all *graphs* (of a given cardinality) via a morphism preserving the value of all its vertices. However, in this work this condition is relaxed; we only require that $U$ embeds all *trees* (of a given cardinality) via a morphism preserving the value of its root.

In the study of positionality, the two definitions (embedding graphs or trees) can be seen to be equivalent: to embed a graph $G$ in a well-monotone (totally ordered) graph $U$, one may first unfold it, then embed the obtained tree, and then obtain a morphism by considering minimal images for each $v \in V(G)$. For a formal exposition, see [Ohl21, Corollary 1.1]. Therefore notions from this paper indeed collapse with those from [Ohl23] in the case of positionality (that is, memory $\mu = 1$).

When $U$ is not totally ordered, as in this paper, the two notions however differ; ours (embedding trees) is a strict relaxation of the previous one (embedding graphs). We show in this section that this relaxation is in fact necessary: Lemma 3.4 (and thus, the converse implication in Theorem 3.1) fails when using the stronger definition of universality.

**Proposition 5.5.** There exists a prefix-independent objective $W$ with $\epsilon$-memory $\le 2$ such that for all $m \ge 1$, there is a graph $G_m$ satisfying $W$ such that any monotone graph satisfying $W$ and embedding $G_m$ has width $\ge m$.

*Proof.* Let $C = \{a, b\}$ and

$$ W = \{w \in C^{\omega} \mid w \text{ has infinitely many occurrences of both } a \text{ and } b\} = \text{Muller}(\{a, b\}). $$

For $m \ge 1$ we let $G_m$ be the $C$-graph over $V(G) = m = \{0, \dots, m-1\}$ given by

$$ E(G_m) = \{i \xrightarrow{a} j \mid i < j\} \cup \{j \xrightarrow{b} i \mid i < j\}. $$

Graph $G_m$ is represented in Figure 19. Note that it indeed satisfies $W$.

<figure><img src="image_26.png" /><figcaption>Figure 19: The graph $G_m$ from the proof of Proposition 5.5. As often, some edges are omitted for clarity.</figcaption></figure>

Let $(U, \le)$ be a monotone $C$-graph satisfying $W$ with a morphism $\phi: G_m \to U$; aiming for a contradiction, we assume that $U$ has width $< m$. Since $G_m$ has size $m$, $\phi(V(G_m))$
cannot be an antichain, thus there are $0 \le i < j \le m - 1$ such that $\phi(i)$ and $\phi(j)$ are comparable in $U$.

Assume first that $\phi(i) \le \phi(j)$. Then we have in $U$ that

$$\phi(i) \xrightarrow{a} \phi(j) \ge \phi(i)$$

which gives $\phi(i) \xrightarrow{a} \phi(i)$ by monotonicity. But then $\phi(i) \xrightarrow{a} \phi(i) \xrightarrow{a} \dots$ defines a path in $U$ with colouration $a^\omega$, which contradicts that $U$ satisfies $W$. Then case $\phi(i) \ge \phi(j)$ is dealt with symmetrically by constructing a path of colouration $b^\omega \notin W$. $\square$

## 6. CLOSURE PROPERTIES

### 6.1. Lexicographical products.
In this section, we prove that lexicographic products of objectives are well-behaved with respect to memory; thus extending the result of [Ohl23] about positionality. We will only be working with prefix-independent objectives, thus we adopt the definition of universality for prefix-independent objectives (see Section 3.4.3).

**Lexicographical products.** We provide a study of lexicographical products, as introduced by Ohlmann [Ohl23], whose result we generalize to finite memory bounds.

Given two prefix-independent objectives $W_1$ and $W_2$ over disjoint sets of colours $C_1$ and $C_2$, we define their *lexicographical product* $W_1 \times W_2$ over $C = C_1 \cup C_2$ by

$$W_1 \times W_2 = \{w \in C^\omega \mid [w^2 \text{ is infinite and in } W_2] \text{ or } [w^2 \text{ is finite and } w^1 \in W_1]\},$$

where $w^1$ (resp. $w^2$) is the (finite or infinite) word obtained by restricting $w$ to occurrences of letters from $C_1$ (resp. $C_2$) in the same order. Note that if $w^2$ is finite then $w^1$ is infinite, which is why the product is well defined.

Note that lexicographical products are not commutative: informally, more importance is given to $W_2$ and to colours from $C_2$. They are however associative.

As a well-known example, the *parity condition*

$$\{w \in [0, 2h]^\omega \mid \limsup(w) \text{ is even}\},$$

can be rewritten as a lexicographical product

$$\mathrm{TW}(0) \times \mathrm{TL}(1) \times \mathrm{TW}(2) \times \dots \times \mathrm{TL}(2h - 1) \times \mathrm{TW}(2h),$$

where $\mathrm{TW}(c)$ and $\mathrm{TL}(c)$ are respectively the *trivially winning* and *trivially losing* objectives over $C = \{c\}$, that is

$$\mathrm{TW}(c) = \{c^\omega\} \subseteq C^\omega \text{ and } \mathrm{TL}(c) = \emptyset \subseteq C^\omega.$$

Given two partially ordered sets $(U_1, \le_1)$ and $(U_2, \le_2)$, their *lexicographical product* $\le$ is defined over $U = U_1 \times U_2$ by

$$(u_1, u_2) \le (u'_1, u'_2) \iff u_2 < u'_2 \text{ or } [u_2 = u'_2 \text{ and } u_1 \le u'_1].$$

If both $\le_1$ and $\le_2$ are well-founded, then so is their lexicographical product $\le$. The following simple property relates antichains in $\le_1$ and $\le_2$ to those in their product.

**Lemma 6.1.** A set $A \subseteq U_1 \times U_2$ defines an antichain in $\le$ if and only if its projection on $U_2$ is an antichain with respect to $\le_2$ and for each fixed $u_2 \in U_2$, $\{u_1 \mid (u_1, u_2) \in A\}$ is an antichain in $U_1$ with respect to $\le_1$. Thus, if $\mu_1$ and $\mu_2$ are upper bounds to the size of antichains in $\le_1$ and $\le_2$, then $\mu_1\mu_2$ is an upper bound to the size of antichains in $\le$.
We now define the lexicographical product $(U, \leq)$ of two ordered graphs $(U_1, \leq_1)$ and $(U_2, \leq_2)$. Intuitively, each vertex in $U_2$ is replaced by a copy of $U_1$ (see also Figure 20.

<figure><img src="image_27.png" /><figcaption>Figure 20: Illustration of the lexicographical product of two ordered graphs.</figcaption></figure>

Formally $U$ is defined over the lexicographical product of $(V(U_1), \leq_1)$ and $(V(U_2), \leq_2)$, that is $V(U) = V(U_1) \times V(U_2)$ and $\leq$ is as above. Its edges are:

$$E(U) = \{(u_1, u_2) \xrightarrow{c_1} (u'_1, u'_2) \mid c_1 \in C_1 \text{ and } (u_2 >_2 u'_2 \text{ or } [u_2 = u'_2 \text{ and } u_1 \xrightarrow{c_1} u'_1])\} \\ \cup \{(u_1, u_2) \xrightarrow{c_2} (u'_1, u'_2) \mid c_2 \in C_2 \text{ and } u_2 \xrightarrow{c_2} u'_2\}.$$

We denote this product by $U = U_1 \times U_2$; it is very robust with respect to the notions under study.

**Lemma 6.2.** If $(U_1, \leq_1)$ and $(U_2, \leq_2)$ are monotone, then so is their lexicographical product $U$.

*Proof.* Let

$$(v_1, v_2) \geq (u_1, u_2) \xrightarrow{c} (u'_1, u'_2) \geq (v'_1, v'_2)$$

in $U$. There are two cases.

* If $c \in C_1$, then again there are two cases.

- If $u_2 > u'_2$, then we have $v_2 \geq u_2 > u'_2 \geq v'_2$ which concludes.

- Otherwise we have $u_2 = u'_2$ and $u_1 \xrightarrow{c} u'_1$. If $v_2 > v'_2$ we conclude immediately. Otherwise, we have $v_2 = v'_2$ and $v_1 \geq u_1 \xrightarrow{c} u'_1 \geq v'_1$ and the result follows from monotonicity in $U_1$.

* If $c \in C_2$, then by definition, $u_2 \xrightarrow{c} u'_2$. Since moreover it holds that $v_2 \geq u_2$ and $u'_2 \geq v'_2$, we conclude thanks to monotonicity in $U_2$. $\square$

We may now state our main result in this section, which is a direct extension of [Ohl23, Theorem 5.2].

**Theorem 6.3.** Let $W_1$ and $W_2$ be two prefix-independent objectives over disjoint sets of colours $C_1$ and $C_2$. Let $\kappa$ be a cardinal and let $(U_1, \leq)$ and $(U_2, \leq)$ be monotone graphs which are respectively $(\kappa, W_1)$ and $(\kappa, W_2)$-universal. Then $U_1 \times U_2$ is monotone and $(\kappa, W_1 \times W_2)$-universal.

Combining with Theorems 3.1 and 3.2 together with Proposition 3.5 and Lemma 6.1, we get the following result.

**Corollary 6.4.** Let $W_1$ and $W_2$ be two prefix-independent objectives over disjoint sets of colours $C_1$ and $C_2$, and assume that $W_1$ (resp. $W_2$) has $\varepsilon$-memory $\leq n_1 \in \mathbb{N}$ (resp. $\leq n_2$). Then, their lexicographical product $W_1 \times W_2$ has $\varepsilon$-memory $\leq n_1 n_2$.
**Products with trivial conditions.** Before moving on to its proof, we discuss a basic but interesting application of Corollary 6.4, namely, that products with trivial conditions preserve $\varepsilon$-memory. Let $W \subseteq C^\omega$ be an objective with finite $\varepsilon$-memory $\le m$, let $a \notin C$ and denote $C^a = C \sqcup \{a\}$. Consider the four conditions $W_1, W_2, W_3$ and $W_4$ over $C^a$ defined by

$$ 
\begin{align*}
W_1 &= W \ltimes \mathrm{TL}(a) &= \{w \in (C^a)^\omega \mid |w_a| < \infty \text{ and } w_C \in W\} \\
W_2 &= W \ltimes \mathrm{TW}(a) &= \{w \in (C^a)^\omega \mid |w_a| = \infty \text{ or } w_C \in W\} \\
W_3 &= \mathrm{TL}(a) \ltimes W &= \{w \in (C^a)^\omega \mid w_C = \infty \text{ and } w_C \in W\} \\
W_4 &= \mathrm{TW}(a) \ltimes W &= \{w \in (C^a)^\omega \mid w_C < \infty \text{ or } w_C \in W\}.
\end{align*}
$$

By Corollary 6.4, since $\mathrm{TL}(a)$ and $\mathrm{TW}(a)$ are positional, each of these four objectives has $\varepsilon$-memory $\le m$. The first two objectives have sometimes been called respectively $W \wedge \mathrm{CoBuchi}(a)$ and $W \vee \mathrm{Buchi}(a)$ in the literature, and it was known from the work of Kopcyński [Kop08] that these operations preserve positionality. However, the stronger result we establish (preservation of $\varepsilon$-memory) is new, as far as we are aware.

**Proof of Theorem 6.3.** The proof of Theorem 6.3 is similar to that of Ohlmann [Ohl23, Theorem 5.2], we give full details for completeness. The remainder of the section is devoted to the proof.

Fix $W_1, W_2, C_1, C_2, \kappa, (U_1, \le_1)$ and $(U_2, \le_2)$ as in the statement of Theorem 6.3, and let $C = C_1 \sqcup C_2$, $U = U_1 \ltimes U_2$ and $W = W_1 \ltimes W_2$. We need to show that $U$ satisfies $W$, and that it embeds all pretrees of cardinality $< \kappa$ which satisfy $W$.

**Claim 6.5.** The graph $U$ satisfies $W$.

*Proof of the claim.* Consider an infinite path

$$ \pi = u^0 \xrightarrow{c^0} u^1 \xrightarrow{c^1} \dots $$

in $U$, and for each $i$ let us denote $u^i = (u_1^i, u_2^i)$. Assume first that there are only finitely many $c^i$'s which belong to $C_2$, and let $i_0$ be such that $c^i \in C_1$ for all $i \ge i_0$.

Then by definition of $C_1$-edges in $U$, it holds that

$$ u_2^{i_0} \geq_2 u_2^{i_0+1} \geq_2 u_2^{i_0+2} \geq_2 \dots $$

Thus by well-foundedness of $\le_2$, the $u_2^{i_0+i}$ are constant after some point, say for $i \ge i_1$. Thus it holds that

$$ u_1^{i_1} \xrightarrow{c^{i_1}} u_1^{i_1+1} \xrightarrow{c^{i_1+1}} \dots $$

is a path in $U_1$, and therefore $c_1^i c_1^{i+1} \dots \in W_1$. We conclude in this case that $\pi$ indeed satisfies $W$ by prefix-independence.

Hence we now assume that there are infinitely many $c^i$'s which belong to $C_2$, and let $i_0 < i_1 < \dots$ denote exactly these occurrences. Then we have for all $j$ that all $c^i$'s with $i \in [i_j + 1, i_{j+1} - 1]$ belong to $C_1$ and thus by definition of $U$ it holds that $u_2^{i_j+1} \ge u_2^{i_j+1}$. Hence we have in $U_2$

$$ u_2^{i_0} \xrightarrow{c^{i_0}} u_2^{i_0+1} \geq_2 u_2^{i_1} \xrightarrow{c^{i_1}} u_2^{i_1+1} \geq_2 \dots, $$

and thus by monotonicity of $U_2$,

$$ u_2^{i_0} \xrightarrow{c^{i_0}} u_2^{i_1} \xrightarrow{c^{i_1}} \dots $$

is a path in $U_2$. Since $U_2$ satisfies $W_2$, we conclude that $\pi$ satisfies $W$.

<$
We now show that $U$ embeds all $C$-pretrees of cardinality $< \kappa$ which satisfy $W$; let $T$ be such a pretree, and let $t_0$ denote its root. Let us partition $V(T)$ according to colours of incoming edges, that is, we let

$$V_2 = \{t_0\} \cup \{t \in V(T) \mid \exists t' \in V(T) \text{ and } c_2 \in C_2 \text{ with } t' \xrightarrow{c_2} t \in E(T)\} \\ \text{and } V_1 = \{t \in V(T) \mid \exists t' \in V(T) \text{ and } c_1 \in C_1 \text{ with } t' \xrightarrow{c_1} t \in E(T)\}.$$

Note that indeed we have $V(T) = V_1 \cup V_2$. For each $t \in V(T)$, we moreover define the $V_2$-ancestor of $t$, denoted $anc_2(t) \in V_2$, to be the closest ancestor of $t$ belonging to $V_2$, that is, the unique $t' \in V_2$ with a path of $C_1$-edges towards $t$ in $T$; note that for $t \in V_2$ we have $anc_2(t) = t$.

We now define a $C_2$-pretree $T_2$ rooted at $t_0$ by contracting the $C_1$-edges in $T$, formally we let $V(T_2) = V_2$ and

$$E(T_2) = \{t \xrightarrow{c_2} t' \mid t \xrightarrow{C_1^* c_2} t'\}.$$

**Claim 6.6.** The $C_2$-pretree $T_2$ satisfies $W_2$.

*Proof of the claim.* Let $\pi = t_0 \xrightarrow{c_0} t_1 \xrightarrow{c_1} \dots$ be an infinite path in $T_2$; note that the $c^i$'s belong to $C_2$. Then by definition of $T_2$ we have an infinite path of the form

$$\pi' : t_0 \xrightarrow{C_1^* c_0} t_1 \xrightarrow{C_1^* c_1} \dots$$

in $T$. Since $T$ satisfies $W$ and $\pi'$ has infinitely many occurrences of colours in $C_2$ (namely, exactly the $c^i$'s), we get that $c^0 c^1 \dots \in W_2$ thus $\pi$ satisfies $W_2$. $\triangleleft$

Since moreover $|T_2| \le |T| < \kappa$, there is a morphism $\phi_2 : T_2 \to U_2$. We now partition $V(T)$ according to which element of $U_2$ is assigned to the 2-ancestor of each vertex, formally for each $u_2 \in U_2$, we define

$$V^{u_2} = \{t \in V(T) \mid \phi_2(anc_2(t)) = u_2\}.$$

Note that some $V^{u_2}$'s may be empty, that they partition $V(T)$, and that for each $t \in V_2$ we have $t \in V^{\phi_2(t)}$ since $anc_2(t) = t$.

For each $u_2 \in U_2$, we define $T_1^{u_2}$ to be the restriction of $T$ to vertices in $V^{u_2}$ and to $C_1$-edges. Note that $T_1^{u_2}$ is a disjoint union of pretrees (as is any restriction of a pretree), and that it has colours in $C_1$.

**Claim 6.7.** For any $u_2 \in U_2$, it holds that $T_1^{u_2}$ satisfies $W_1$.

*Proof of the claim.* Since $T_1^{u_2}$ is a restriction of $T$, any path in $T_1^{u_2}$ is also a path in $T$; the result follows because $T$ satisfies $W$ and $W \cap C_1^\omega \subseteq W_1$ (this is actually an equality). $\triangleleft$

Since moreover $|T_1^{u_2}| \le |T| < \kappa$, there exists, for each $u_2 \in U_2$, a morphism $\phi_1 : T_1^{u_2} \to U_1$. We are finally ready to define $\phi : V(T) \to U$ to be given by

$$\phi(t) = (\phi_1^{u_2}(t), u_2),$$

where $u_2$ is such that $t \in V_{u_2}$ (that is, $u_2 = \phi_2(anc_2(t))$). The following claim concludes the proof of Theorem 6.3.

**Claim 6.8.** The map $\phi : T \to U$ defines a morphism.

*Proof of the claim.* We should check that any edge in $T$ is mapped to an edge in $U$; there are two cases depending on the colour of the edge.
• Consider an edge $t \xrightarrow{c_1} t' \in E(T)$ with $c_1 \in C_1$. Then $t$ and $t'$ have the same 2-ancestor, and therefore $t \xrightarrow{c_1} t'$ is an edge in $T_1^{u_2}$ for $u_2 = \phi_2(\text{anc}_2(t))$. Since $\phi_1^{u_2} : T_1^{u_2} \to U_1$ is a morphism, it follows that $\phi_1^{u_2}(t) \xrightarrow{c_1} \phi_1^{u_2}(t') \in E(U_1)$. Hence by definition of $U$, it indeed holds that $\phi(t) \xrightarrow{c_1} \phi(t') = (\phi_1^{u_2}(t), u_2) \xrightarrow{c_1} (\phi_1^{u_2}(t), u_2) \in E(U)$.

• Consider now an edge $t \xrightarrow{c_2} t' \in E(T)$ with $c_2 \in C_2$. Then $t' \in V_2$. Let $t_0 = \text{anc}_2(v)$, and observe that $t_0 \xrightarrow{c_2} t' \in E(T_2)$. Thus since $\phi_2 : T_2 \to U_2$ is a morphism, it follows that $\phi_2(t_0) \xrightarrow{c_2} \phi_2(t') \in E(U_2)$ thus by definition of $U$ we get that $\phi(t) \xrightarrow{c_2} \phi(t') = (u_1, \phi_2(t_0)) \xrightarrow{c_2} (u'_1, \phi_2(t')) \in E(U)$ (regardless of $u_1$ and $u'_1$).

This concludes the proof. ◁

## 6.2. Combining objectives with locally finite memory.
In this section, we investigate properties of objectives which have $\varepsilon$-free memory < $\aleph_0$. This means that for any $\varepsilon$-free game there is an optimal strategy $S$ such that for all vertices $v$, the amount of memory used at $v$ (that is, the cardinality of $\pi_S^{-1}(v)$) is finite; however it may be that there is no uniform finite bound on the $|\pi_S^{-1}(v)|$'s, even when the game is fixed. We call this property *locally finite memory*. An example is discussed in Figure 21.

We remark that this notion is only interesting in the case of $\varepsilon$-free memory, and not in that of $\varepsilon$-memory. By Proposition 2.2, if the $\varepsilon$-memory of an objective is < $\aleph_0$, then it is $\le n$ for some $n \in \mathbb{N}$.

<figure><img src="image_28.png" /><figcaption>Figure 21: A game where initially, Adam chooses an upper bound $i$, then the players alternate in choosing integers in $[-i, i]$. Eve wins if the partial sums of the weights remain bounded both from above and below (bi-boundedness objective). She can ensure a win by simply playing the opposite of Adam in each round (this strategy is represented on the right-hand side), which requires unbounded but locally finite memory. Since bi-boundedness objectives are intersections of two positional objectives (being bounded from above and from below), our results in this section ensure that any game with a bi-boundedness objective has optimal locally finite memory strategies.</figcaption></figure>

Note that, when applied to $\mu = \aleph_0$, since well-founded orders with bounded antichains correspond to well-quasi-orders (wqo's), Theorem 3.2 states that the existence of universal monotone graphs which are wqo's for a given objective (or even, a valuation) entails locally finite memory. Unfortunately this is not a characterisation: Proposition 5.1 applied to $\mu = \aleph_0$ gives an objective with $\varepsilon$-free memory 2 but which does not admit such universal structures.
Still, by combining our knowledge so far with a few additional insights stated below, we may derive some strong closure properties pertaining to this class of objectives. In the sequel, we will simply say *monotone wqo* for a well-monotone graph whose antichains are finite.

Given two partially ordered sets $(U_1, \leq_1)$ and $(U_2, \leq_2)$, we define their (*direct*) product to be the partially ordered set $(U_1 \times U_2, \leq)$, where

$$ (u_1, u_2) \leq (u'_1, u'_2) \iff [u_1 \leq u'_1] \text{ and } [u_2 \leq u'_2]. $$

Note that if $\leq_1$ and $\leq_2$ are well-founded, then so is $\leq$. However, there may be considerable blowup on the size of antichains, for instance, $\omega \times \omega$ has arbitrarily large antichains whereas $\omega$ is a total order. However, it is a well-known fact from the theory of wqo's (see for instance [DFGL+17]) that, assuming well-foundedness, one may not go from finite to infinite antichains.

**Lemma 6.9 (Folklore).** If $(U_1, \leq_1)$ and $(U_2, \leq_2)$ are wqo's, then so is their product.

Given two partially ordered C-graphs $(G_1, \leq_1)$ and $(G_2, \leq_2)$, we define their (*direct*) product to be the partially ordered C-graph $G$ defined over the product of $(V(G_1), \leq_1)$ and $(V(G_2), \leq_2)$ by

$$ E(G) = \{(v_1, v_2) \xrightarrow{c} (v'_1, v'_2) \mid v_1 \xrightarrow{c} v'_1 \in E(G_1) \text{ and } v_2 \xrightarrow{c} v'_2 \in E(G_2)\}. $$

Note that if $(G_1, \leq_1)$ and $(G_2, \leq_2)$ are monotone, then so is their product. Therefore, if $(G_1, \leq_1)$ and $(G_2, \leq_2)$ are monotone wqo's, then so is their product. Our discussion hinges on the following simple result.

**Lemma 6.10.** Let $\kappa$ be a cardinal, and $W_1, W_2 \subseteq C^\omega$ be two objectives. Let $(U_1, \leq_1)$ and $(U_2, \leq_2)$ be two C-graphs which are $(\kappa, W_1)$ and $(\kappa, W_2)$-universal, respectively. Then their product $U$ is $(\kappa, W_1 \cap W_2)$-universal.

*Proof.* Let $T$ be a tree with cardinality $< \kappa$, by assumption there exist two morphisms $T \xrightarrow{\phi_1} U_1$ and $T \xrightarrow{\phi_2} U_2$ which preserve the value at the root $t_0$. We prove that $\phi = (\phi_1, \phi_2): t \mapsto (\phi_1(t), \phi_2(t)) \in V(U)$ defines a morphism from $T$ to $U$ which preserves the value at $t_0$.

Let $t \xrightarrow{c} t' \in E(T)$, then for both $i \in \{1, 2\}$ since $\phi_i$ is a morphism it holds that $\phi_i(t) \xrightarrow{c} \phi_i(t') \in E(U_i)$ and therefore by definition of $U$, $\phi(t) \xrightarrow{c} \phi(t') \in E(U)$ thus $\phi$ is a morphism. Now any path from $\phi(t_0)$ in $U$ projects to a path from $\phi_1(t_0)$ in $U_1$, and to a path from $\phi_2(t_0)$ in $U_2$. Thus since $\phi_1$ and $\phi_2$ preserve the value at $t_0$ then so does $\phi$. $\square$

Therefore, by combining Lemma 6.9 with the above one, we obtain that if two objectives $W_1$ and $W_2$ have monotone wqo's as universal graphs, then so does their intersection, hence from Theorem 3.2, $W_1 \cap W_2$ has locally finite memory. In particular, thanks to Theorem 3.1, we get the following weak closure property.

**Corollary 6.11.** Let $W_1$ and $W_2$ be two objectives which have monotone wqo's as universal graphs. Then so does $W_1 \cap W_2$. In particular the intersection of two objectives with finite $\varepsilon$-memory has locally finite memory.

The upper bound stated in the corollary is met: bi-boundedness objectives (see Figure 21) give an example where $W_1$ and $W_2$ are positional but $W_1 \cap W_2$ does not have finite memory (only locally finite). Note moreover that it is not true that the intersection of two objectives with finite $\varepsilon$-memory has $\varepsilon$-memory < $\aleph_0$ (bi-boundedness objectives are an example). Although our results fall short of implying such a strong closure property, we may still state the following conjecture.
**Conjecture 6.12.** Objectives with locally finite memory are closed under intersection.

Finally, observe that if an objective has locally finite memory, then it holds that for all finite games there is a strategy with finite (bounded) memory. One may wonder if the converse statement is true; unfortunately this is not the case; a counterexample is given by the condition

$$W = \left\{ w_0 w_1 \cdots \in \{-1, 0, 1\}^{\omega} \mid \exists k \in \mathbb{N}, \sum_{i=0}^{k-1} w_i \le -1 \right\}.$$

Indeed, one can prove that this objective has finite memory over finite games, however, Eve requires (locally) infinite memory to win the game where Adam picks an arbitrary number $i \in \mathbb{N}$ (this is simulated by a chain of 1-edges), and Eve replies with an arbitrary $j \in -\mathbb{N}$.

**6.3. Unions of prefix-independent $\Sigma_2^0$ objectives.** As already discussed in Section 4.2, the Cantor topology on $C^\omega$ naturally provides a way to define general families of objectives that have been well-studied in the literature of formal languages (we refer to [PP04] for a general overview). In particular, some of these classes of objectives are given by the different levels of the Borel hierarchy; the lowest levels are $\Sigma_1^0$, consisting on the open subsets, and $\Pi_1^0$, consisting on the closed subsets. The level $\Sigma_{n+1}^0$ (resp. $\Pi_{n+1}^0$) contains the countable unions (resp. countable intersections) of subsets in $\Pi_n^0$ (resp. $\Sigma_n^0$).

In this final section, we prove that prefix-independent objectives in $\Sigma_2^0$ with $\varepsilon$-memory $\le m \in \mathbb{N}$ are closed under countable unions. This is closely related to Kopczyński's conjecture, which stipulates that prefix-independent positional objectives are closed under unions; we refer to the conclusion for more discussion. We recall that $\Sigma_2^0$ objectives are those of the form

$$W_{\mathcal{L}} = \{w \in C^{\omega} \mid w \text{ has finitely many prefixes in } \mathcal{L}\},$$

where $\mathcal{L} \subseteq C^*$ is an arbitrary language of finite words [Skr13].

**Theorem 6.13.** *Prefix-independent $\Sigma_2^0$ objectives with $\varepsilon$-memory $\le m \in \mathbb{N}$ are closed under countable unions.*

This generalises$^{14}$ a result of [Ohl23] from positionality to finite memory.

Given a family $(G_\lambda)_{\lambda \in \alpha}$ of $C$-graphs indexed by ordinals, we define their direct sum $G$ to be the disjoint union of the $G_i$, with additionally all $C$-edges pointing from $G_\lambda$ to $G_{\lambda'}$ for $\lambda > \lambda'$; formally

$$E(G) = \bigcup_{\lambda \in \alpha} E(G_\lambda) \cup \{v \xrightarrow{c} v' \mid v \in V(G_\lambda), v' \in V(G'_\lambda) \text{ and } \lambda > \lambda'\}.$$

If the $G_i$'s are (partially) ordered graphs, then the order on their sum is defined to be the concatenation of the orders on the $G_i$'s. Note that if the $G_i$'s are well-ordered then so is their sum, and that if the antichains of the $G_i$'s are $< \mu$ then so are the antichains of their sum. Recall that $G \times \alpha$ denotes the direct sum of $\alpha$ copies of $G$ (which is also the lexicographical product of $G$ and the graph consisting of $\alpha$ vertices and no edges).

Our proof relies on the following lemma.

<footnote>$^{14}$Formally, Ohlmann proved the result for so called “non-healing” objectives, which are slightly more general than $\Sigma_2^0$. Here we chose to prove it only for $\Sigma_2^0$, but the proof is essentially the same, and can easily be adapted to non-healing objectives.</footnote>
**Lemma 6.14.** Let $W_0, W_1, \dots \subseteq C^\omega$ be prefix-independent $\Sigma_2^0$ objectives, $\kappa$ be a cardinal, and $U_0, U_1, \dots$ be $C$-graphs such that for each $i$, $U_i$ is $(W_i, \kappa)$-universal. Let $W = \bigcup_i W_i$. Then the graph $U \times \kappa$, where $U$ is the direct sum of the $U_i$'s, is $(\kappa, W)$-universal.

*Proof.* Thanks to Lemma 3.8, it suffices to prove that $U$ is almost $(\kappa, W)$-universal. Let $T$ be a tree of cardinality $< \kappa$ satisfying $W$. We show that there exists $i \in \mathbb{N}$ and $t \in T$ such that $T[t]$ satisfies $W_i$; this implies the result since by universality of $U_i$ we then get $T[t] \to U_i \to U$. Assume otherwise. Take $e = e_0 e_1 \dots \in \mathbb{N}^\omega$ to be a word over the naturals with infinitely many occurrences of each natural, for instance $e = 010120123\dots$. For each $i \in \mathbb{N}$, let $\mathcal{L}_i \subseteq C^*$ be such that $W_i = \{w \in C^\omega \mid w \text{ has finitely many prefixes in } \mathcal{L}_i\}$.

We now construct an infinite path $\pi = \pi_0\pi_1\dots$ starting from the root $t_0$ in $T$ such that for each $i$, the coloration $w_0\dots w_i$ of $\pi_0\dots\pi_i$ belongs to $\mathcal{L}_{e_i}$. This implies that the coloration $w$ of $\pi$ has infinitely many prefixes in each of the $\mathcal{L}_i$'s, therefore it does not belong to $W$, a contradiction. Assume $\pi = \pi_0\dots\pi_{i-1} : t_0 \stackrel{w_0\dots w_{i-1}}{\rightsquigarrow} t$ constructed up to $\pi_{i-1}$. Since by assumption, $T[t]$ does not satisfy $W_{e_i}$, there is a path $\pi' : t \stackrel{w}{\rightsquigarrow}$ such that $w \notin W_{e_i}$. By prefix-independence of $W_{e_i}$, we get $w_0\dots w_{i-1}w \notin W_{e_i}$, thus $w$ has a prefix $w_i$ such that $w_0\dots w_{i-1}w_i \in \mathcal{L}_{e_i}$; this allows us to augment $\pi$ as required and conclude our proof. $\square$

The theorem follows from combining Lemma 6.14, Theorem 3.1 and Proposition 3.5, and the fact that antichains in the well-founded graph $U \times \kappa$ are no larger than those in $U$.

## 7. CONCLUSION

In this paper, we have extended Ohlmann's work [Ohl23] to the study of the memory of objectives. We have introduced different variants of well-monotone universal graphs adequate to the various models of memory appearing in the literature, and we have characterised the memory of objectives through the existence of such universal graphs (Theorems 3.1 and 3.2).

**Possible applications.** We expect these results to have two types of applications. The first one is helping to find tight bounds for the memory of different families of objectives. We have illustrated this use of universal graphs by recovering known results about the memory of topologically closed objectives [CFH14] and Muller objectives [DJW97], as well as providing non-trivial tight bounds on the memory of some new concrete examples. While finding universal graphs and proving their correctness might be difficult, we have provided tools to facilitate this task in the important case of prefix-independent objectives (Lemma 3.8).

The second kind of application discussed in the paper is the study of the combinations of objectives. We have used our characterisations to bound the memory requirements of finite lexicographical product of objectives (Section 6.1). We have also established that intersections of objectives with finite $\varepsilon$-memory always have locally finite $\varepsilon$-free memory. Finally, we have proved that prefix-independent $\Sigma_2^0$ objectives with finite $\varepsilon$-memory are closed under countable unions. We believe that the new angle offered by universal graphs will help to better understand general properties of memory.

**Open questions.** Many questions remain open. First of all, as discussed in Section 6.2, we have proved that objectives admitting universal monotone wqo's are closed by intersection. However, we do not know whether the larger class of objectives with unbounded finite $\varepsilon$-free memory is closed under intersection. A related question is therefore understanding what are exactly the objectives admitting universal monotone wqo's.
In the realm of positional objectives, a long-lasting open question is Kopczyński's conjecture [Kop08]: are unions of prefix-independent positional objectives positional? This conjecture has recently been disproved for finite game graphs by Kozachinskiy [Koz22a], but it remains open for arbitrary game graphs. We propose a generalisation of Kopczyński's conjecture in the case of ε-memory.

**Conjecture 7.1.** Let $W_1 \subseteq C^\omega$ and $W_2 \subseteq C^\omega$ be two prefix-independent objectives with $\epsilon$-memory $\le n_1, n_2$, respectively. Then $W_1 \cup W_2$ has $\epsilon$-memory $\le n_1 n_2$.

Objectives that are $\omega$-regular (those recognised by a deterministic parity automaton, or, equivalently, by a non-deterministic Büchi automaton) have received a great deal of attention over the years. Casares and Ohlmann have recently characterised those $\omega$-regular objectives which are positional [CO24], thereby establishing decidability in polynomial time and proving Kopczyński's conjecture for these objectives. Their characterisation crucially relied on Ohlmann's characterisation of positionality via (totally ordered) well-founded monotone universal graphs.

However, very little is known about memory requirements of $\omega$-regular objectives, for instance, the precise memory requirement of a given $\omega$-regular objective is not known to be decidable. We believe that our extension of Ohlmann's universal graphs to the setting of memory paves the way to answering the above question in the positive (possibly, even obtaining a polynomial-time decision procedure$^{15}$).

Similarly, one may turn to (non-necessarily $\omega$-regular) objectives with topological properties, for instance, it is not known by now which topologically open objectives (or, recognised by infinite deterministic reachability automata) are positional, or finite memory. We hope that the newly available tools presented in this paper will also help progress in this direction.

## ACKNOWLEDGMENT

The authors wish to acknowledge fruitful discussions with Nathanaël Fijalkow, Rémi Morvan and Pierre Vandenhove.

## REFERENCES

[BCRV24] Patricia Bouyer, Antonio Casares, Mickael Randour, and Pierre Vandenhove. Half-positional objectives recognized by deterministic Büchi automata. *Log. Methods Comput. Sci.*, 20(3), 2024. doi:10.46298/LMCS-20(3:19)2024.

[BFRV23] Patricia Bouyer, Nathanaël Fijalkow, Mickael Randour, and Pierre Vandenhove. How to play optimally for regular objectives? In *ICALP*, volume 261, pages 118:1–118:18, 2023. doi:10.4230/LIPICS.ICALP.2023.118.

[BORV23] Patricia Bouyer, Youssouf Oualhadj, Mickael Randour, and Pierre Vandenhove. Arena-independent finite-memory determinacy in stochastic games. *Log. Methods Comput. Sci.*, 19(4), 2023. doi:10.46298/LMCS-19(4:18)2023.

[BRO$^{+}$22] Patricia Bouyer, Stéphane Le Roux, Youssouf Oualhadj, Mickael Randour, and Pierre Vandenhove. Games where you can play optimally with arena-independent finite memory. *Log. Methods Comput. Sci.*, 18(1), 2022. doi:10.46298/lmcs-18(1:11)2022.

<footnote>$^{15}$There is no hope for a polynomial-time decision procedure in the case of chromatic memory, as the problem of deciding whether the chromatic memory of an objective is $\le k$ is known to be NP-hard already for simple subclasses of $\omega$-regular languages [Cas22, BFRV23].</footnote>
[BRV23] Patricia Bouyer, Mickael Randour, and Pierre Vandenhove. Characterizing omega-regularity through finite-memory determinacy of games on infinite graphs. *TheoretiCS*, 2, 2023. doi: 10.46298/THEORETICS.23.1.

[Cas22] Antonio Casares. On the minimisation of transition-based Rabin automata and the chromatic memory requirements of Muller conditions. In *CSL*, volume 216, pages 12:1–12:17, 2022. doi: 10.4230/LIPIcs.CSL.2022.12.

[CCFL24] Antonio Casares, Thomas Colcombet, Nathanaël Fijalkow, and Karoliina Lehtinen. From Muller to parity and Rabin automata: Optimal transformations preserving (history) determinism. *TheoretiCS*, 3, 2024. doi:10.46298/THEORETICS.24.12.

[CCL22] Antonio Casares, Thomas Colcombet, and Karoliina Lehtinen. On the size of good-for-games Rabin automata and its link with the memory in Muller games. In *ICALP*, volume 229, pages 117:1–117:20, 2022. doi:10.4230/LIPIcs.ICALP.2022.117.

[CF18] Thomas Colcombet and Nathanaël Fijalkow. Parity games and universal graphs. *CoRR*, abs/1810.05106, 2018. arXiv:1810.05106.

[CF19] Thomas Colcombet and Nathanaël Fijalkow. Universal graphs and good for games automata: New tools for infinite duration games. In *FoSSaCS*, pages 1–26, 2019. doi:10.1007/978-3-030-17127-8\_1.

[CFH14] Thomas Colcombet, Nathanaël Fijalkow, and Florian Horn. Playing safe. In *FSTTCS*, volume 29, pages 379–390, 2014. doi:10.4230/LIPICS.FSTTCS.2014.379.

[CN06] Thomas Colcombet and Damian Niwiński. On the positional determinacy of edge-labeled games. *Theor. Comput. Sci.*, 352(1-3):190–196, 2006. doi:10.1016/j.tcs.2005.10.046.

[CO23] Antonio Casares and Pierre Ohlmann. Characterising memory in infinite games. In *ICALP*, volume 261 of *LIPIcs*, pages 122:1–122:18, 2023. doi:10.4230/LIPICS.ICALP.2023.122.

[CO24] Antonio Casares and Pierre Ohlmann. Positional $\omega$-regular languages. In *LICS*, pages 21:1–21:14. ACM, 2024. doi:10.1145/3661814.3662087.

[DFGL$^{+}$17] Stéphane Demri, Alain Finkel, Jean Goubault-Larrecq, Sylvain Schmitz, and Philippe Schnoebelen. Well-quasi-orders for algorithms. Lecture notes, Master MPRI, 2017. URL: https://wikimpri.dptinfo.ens-cachan.fr/lib/exe/fetch.php?media=cours:upload: poly-2-9-1v02oct2017.pdf.

[Dil50] Robert P. Dilworth. A decomposition theorem for partially ordered sets. *Annals of Mathematics*, 51(1):161–166, 1950. doi:10.2307/1969503.

[DJW97] Stefan Dziembowski, Marcin Jurdzinski, and Igor Walukiewicz. How much memory is needed to win infinite games? In *LICS*, pages 99–110. IEEE Computer Society, 1997. doi:10.1109/LICS. 1997.614939.

[GH82] Yuri Gurevich and Leo Harrington. Trees, automata, and games. In *STOC*, page 60–65, 1982. doi:10.1145/800070.802177.

[GZ05] Hugo Gimbert and Wiesław Zielonka. Games where you can play optimally without any memory. In *CONCUR*, volume 3653 of *Lecture Notes in Computer Science*, pages 428–442. Springer, 2005. doi:10.1007/11539452\_33.

[Hor08] Florian Horn. *Random Games*. PhD thesis, Université Denis Diderot - Paris 7 & Rheinisch-Westfälische Technische Hochschule Aachen, 2008.

[Kop08] Eryk Kopczyński. *Half-positional Determinacy of Infinite Games*. PhD thesis, Warsaw University, 2008.

[Koz22a] Alexander Kozachinskiy. Energy games over totally ordered groups. *CoRR*, abs/2205.04508, 2022. doi:10.48550/arXiv.2205.04508.

[Koz22b] Alexander Kozachinskiy. Infinite separation between general and chromatic memory. *CoRR*, abs/2208.02691, 2022. doi:10.48550/arXiv.2208.02691.

[Koz22c] Alexander Kozachinskiy. State complexity of chromatic memory in infinite-duration games. *CoRR*, abs/2201.09297, 2022. arXiv:2201.09297.

[Kri71] Jean-Louis Krivine. *Introduction to Axiomatic Set Theory*. Dordrecht, Netherland: Springer, 1971.

[Ohl21] Pierre Ohlmann. *Monotonic graphs for parity and mean-payoff games*. PhD thesis, Université de Paris, 2021.

[Ohl23] Pierre Ohlmann. Characterizing positionality in games of infinite duration over infinite graphs. *TheoretiCS*, 2, 2023. doi:10.46298/THEORETICS.23.3.
[Per63] Micha A. Perles. On Dilworth's theorem in the infinite case. *Israel Journal of Mathematics*, 1(1):108-109, 1963. doi:10.1007/BF02759806.

[PP04] Dominique Perrin and Jean-Éric Pin. *Infinite words - automata, semigroups, logic and games*, volume 141 of *Pure and applied mathematics series*. Elsevier Morgan Kaufmann, 2004.

[Skr13] Michał Skrzypczak. Topological extension of parity automata. *Information and Computation*, 228-229:16-27, 2013. doi:10.1016/j.ic.2013.06.004.

[Zie98] Wiesław Zielonka. Infinite games on finitely coloured graphs with applications to automata on infinite trees. *Theoretical Computer Science*, 200(1-2):135-183, 1998.

# APPENDIX A. SOME NOTES ON SET THEORY

This appendix collects standard definitions and notations concerning basic set theory, as well as some results used throughout the paper. In all the paper, the axiom of choice is accepted. A reference for all the results stated in this appendix is the book [Kri71].

## A.1. Orders and preorders.
A binary relation $\le$ over a set $A$ is a *preorder* (resp. *strict preorder*) if it is reflexive ($\forall x, x \le x$) (resp. it is anti-reflexive, $\forall x, x \not\le x$) and transitive ($x \le y$ and $y \le z$ implies $x \le z$). Given a preorder $\le$, we note < the strict preorder defined by: $x < y$ if $x \le y$ and $x \neq y$. A preorder (resp. *strict preorder*) is an *order* (resp. *strict order*) if it is antisymmetric ($x \le y$ and $y \le x$ implies $x = y$). A *(pre)ordered set* ($A, \le$) is a set together with a *(pre)order* relation.

We say that two elements $x, y$ of a preordered set are *comparable* if $x \le y$ or $y \le x$. A *(pre)order* over $A$ is a *total (pre)order* (also called a *linear order*) if any two elements of $A$ are comparable. If we want to emphasize that an order relation is not necessarily total, we may call it a *partial order*.

A *chain* of an ordered set ($A, \le$) is a subset $S \subseteq A$ whose elements are pairwise comparable. An *antichain* of an ordered set ($A, \le$) is a subset $S \subseteq A$ whose elements are pairwise incomparable ($\forall x, y \in S, x \not\le y$ and $y \not\le x$).

Let ($A, \le$) be an ordered set. A *maximal* (resp. *minimal*) *element* of $S$ is an element $m \in S$ such that $\forall x \in S, m \le x$ (resp. $x \le m$) implies $m \le x$ (resp. $x \le m$). An element $a \in A$ is a *supremum* (resp. *infimum*) of $S$ if $\forall x \in S, x \le a$ (resp. $\forall x \in S, a \le x$ and for any other $b \in A$ with this property $a \le b$ (resp. $b \le a$)). Suprema and infima of ordered sets are unique, but they do not necessarily exist. If the supremum (resp. infimum) of a set $S$ belongs to $S$, it is called a *maximum* (resp. *minimum*).

A *lattice* is an ordered set in which all nonempty finite subsets have both a supremum and an infimum. A complete lattice is an ordered set in which all non-empty subsets have both a supremum and an infimum. We add the adjective *linear* if the order is total.

A partially preordered set ($A, \le$) is *well-founded* if any non-empty subset has a minimal element; or equivalently, if it has no infinite strictly decreasing sequence. A well-founded (strict) total order is called a *(strict) well-order*. A preordered set (resp. ordered set) ($A, \le$) is a *well-quasi order* (wqo) if it is well-founded and has no infinite antichains (equivalently, if any infinite sequence of elements contains an increasing pair).

Two ordered sets ($A, \le_1$), ($B, \le_2$) are *order isomorphic* if there exists an order preserving bijection between them, that is, a bijection $\phi: A \to B$ such that for all $x, y \in A, x \le_1 y$ implies $\phi(x) \le_2 \phi(y)$ and for all $x, y \in B, x \le_2 y$ implies $\phi^{-1}(x) \le_1 \phi^{-1}(y)$

**Proposition A.1** (Well-ordering principle). Any set admits a *well-ordering*.
**Proposition A.2 (Dilworth's Theorem [Dil50]).** Let $(A, \leq)$ be a partially ordered set. If the size of the antichains of $(A, \leq)$ is bounded by a finite number $k$, there are $k$ disjoint chains $S_1, \dots, S_k \subseteq A$, $S_i \cap S_j = \emptyset$ for $i \neq j$, such that $A = \bigcup_{i=1}^k S_i$.

A.2. **Ordinals and cardinals.** Intuitively, the class of ordinals is defined so that it contains one ordinal for each possible well-ordered set, up to isomorphism.

Formally, a set $\alpha$ is an *ordinal* if

(1) The membership relation $\in$ is a strict well-order over $\alpha$.

(2) If $x \in \alpha$, then $x \subsetneq \alpha$.

For example, $\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}, \{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}, \dots$ are ordinals, that we write $0, 1, 2, 3, \dots$. The first infinite ordinal is represented by $\omega = \{0, 1, 2, 3, \dots\}$.

Some important properties of ordinals are:

* The collection of all ordinals is well-ordered by the relation of membership. This is the order that we will consider over this class.

* A well-ordered set is order-isomorphic to one and only one ordinal.

**Proposition A.3 (Transfinite recursion).** Let $P(x)$ be a property about ordinals. Property P holds for every ordinal if and only if it is true that:

For all ordinal $\alpha$, if $P(\beta)$ holds for every $\beta < \alpha$ then $P(\alpha)$ holds.

Two sets are said to be *equinumerous* if there exists a bijection between them. The relation of equinumerousity is an equivalence relation (reflexive, symmetric and transitive). Just as the class of ordinals is defined to contain a representative for any well-ordered set up to isomorphism, the class of cardinals is defined to contain one representative for each equivalence class of the equinumerousity relation.

Formally, a *cardinal* is defined to be an ordinal $\alpha$ that is not equinumerous to any strictly smaller ordinal $\beta < \alpha$. The *cardinality* of a set $A$ is the only cardinal equinumerous to $A$ (equivalently, the smallest ordinal equinumerous to $A$). We denote it by $|A|$.

All finite ordinals are cardinals $(0, 1, 2, \dots)$. The first infinite cardinal is $\omega$. However, when we use it in a context where we are interested in its properties as a cardinal and not in its order, we will denote it by $\aleph_0$.

We remark that cardinals, as well as ordinals, are sets. We will often use them to build graphs or other structures and use expressions as "let $\kappa$ be a cardinal and let $x \in \kappa$".

Some important facts about cardinals are:

* The class of cardinals is well-ordered by membership. This is the order induced by the class of ordinals; in particular we can compare ordinals and cardinals.

* Let $\alpha$ be a cardinal. Its *successor cardinal* is the smallest cardinal that is strictly greater than $\alpha$, it is denoted $\alpha^+$.

* The sum of cardinals coincides with that of natural numbers over finite cardinals. If $\alpha$ and $\beta$ are cardinals and at least one of them is infinite, then $\alpha + \beta = \max\{\alpha, \beta\}$. In particular, if $\alpha$ is infinite, $\alpha + 1 = \alpha$.

* The product of cardinals coincides with that of natural numbers over finite cardinals. If $\alpha$ and $\beta$ are cardinals and at least one of them is infinite, then $\alpha \times \beta = \max\{\alpha, \beta\}$.
## APPENDIX B. TIGHT BOUNDS FOR EXAMPLES FROM SECTION 4

In this appendix we provide the proofs of the bounds appearing in Table 1 that we have not included in the main document.

**Objective W<sub>2</sub>** = {w<sub>0</sub>w<sub>1</sub>w<sub>2</sub> ... ∈ C<sup>ω</sup> | ∀i w<sub>i</sub> ≠ w<sub>i+1</sub>}.

**Proposition B.1.** *The ε-free chromatic memory of W<sub>2</sub> is ≥ |C|, and therefore, also its ε-chromatic memory.*

*Proof.* (We suppose |C| ≥ 2, since the result is trivial for |C| = 1.) Let L = {u ∈ C* | ∀i u<sub>i</sub> ≠ u<sub>i+1</sub>} ⊆ C* (we remark that W<sub>2</sub> = Safe(L<sup>c</sup>)). We consider the game G = (G, V<sub>Eve</sub>, v<sub>0</sub>, W<sub>2</sub>) given by:

* V<sub>Eve</sub> = {v<sub>c,c'</sub> | c, c' ∈ C, c ≠ c'},

* V(G) = {v<sub>u</sub> | u ∈ L} ⊔ V<sub>Eve</sub>,

* v<sub>0</sub> = v<sub>ε</sub>,

* v<sub>u</sub> a → v<sub>ua</sub> for all u ∈ L and all a ∈ C different from the last colour in u.

* v<sub>u</sub> a → v<sub>c,c'</sub> for all u ∈ L and all a, c, c' ∈ C such that c ≠ c',

* v<sub>c,c'</sub> c → v<sub>c,c'</sub> and v<sub>c,c'</sub> c' → v<sub>c,c'</sub> for all c ≠ c'.

That is, Adam starts by picking a finite word $u \in L$ that is safe for the objective, and he chooses a subset of size 2 of C. Then, Eve will have the opportunity to choose between these two colours. It is clear that Eve wins this game: no matter Adam's choice, she will have an option to extend the chosen word with a colour different from the last colour of u, and then she just has to alternate between the two available colours for the rest of the play.

We now prove that she cannot win with a chromatic strategy with memory < |C|.

Let $S = (S, \pi_S, s_0)$ be a chromatic product strategy over a set $M$, that is, $V(S) \subseteq V(G) \times M$ and there is an update function $\delta$: $M \times C \to M$ giving the transitions in the second component of the strategy. Let $s_0 = (v_0, m_0)$. Suppose that its memory is < $|C|$, that is, for all $v \in V(G)$, $|\pi_S^{-1}(v)| < |C|$.

First, we claim that we can suppose $|M| = |\pi_S^{-1}(v_{c,c'})| < |C|$. Indeed, without loss of generality we can restrict the strategy to the set of vertices $(v, m)$ that are accessible from $s_0 = (v_0, m_0)$ by reading words in $L$. For any $v_u \in V_{Adam}$, there is only one such vertex, and for any $v_{c,c'}$, the set of $m \in M$ such that $(v_{c,c'}, m)$ is accessible in that way is independent from the choice of $c$ and $c'$, so we can just suppose that $M$ is the set of such memory states.

By the pigeonhole principle, there is some memory state $m \in M$ and two different colours $c_1, c_2 \in C$ such that there are states $m_1, m_2$ and transitions $\delta(m_1, c_1) = m$ and $\delta(m_2, c_2) = m$. Therefore, in the strategy we can find the following two paths:

$$ (v_0, m_0) \xrightarrow{u_1} (v_{u_1}, m_1) \xrightarrow{c_1} (v_{c_1, c_2}, m), $$

$$ (v_0, m_0) \xrightarrow{u_2} (v_{u_2}, m_2) \xrightarrow{c_2} (v_{c_1, c_2}, m). $$

The strategy must contain either the edge $(v_{c_1,c_2}, m) \xrightarrow{c_1}$ or the edge $(v_{c_1,c_2}, m) \xrightarrow{c_2}$. In both cases we have found a path in $S$ that does not satisfy the objective $W_2$. $\square$

**Objective W<sub>4</sub>** = $\infty(bb) \cup (\neg\infty(b) \cap \neg\infty(aa))$ **over C** = {a, b, c}.

**Proposition B.2.** *A minimal deterministic parity automaton recognising W<sub>4</sub> has 3 states.*
*Proof.* A deterministic parity automaton for $W_4$ with 3 states was shown in Figure 13.

We prove that a parity automaton with 2 states cannot recognise $W_4$. Let $\mathcal{A}$ be a deterministic parity automaton with two states $\{q, p\}$. We remark that a parity automaton recognising $W_4$ must verify that, from any state $s$, if the run of two words $w, w' \in C^\omega$ from $s$ use the same set of transitions, then $w \in W_4 \iff w' \in W_4$.

We first claim that if $\mathcal{A}$ recognises $W_4$, then its restriction to transitions labelled by $a$ and $c$ must be strongly connected. Indeed, if this was not the case, there would be a state $s$ such that $s \xrightarrow{a} s$ and $s \xrightarrow{c} s$, and therefore $\mathcal{A}$ could not differentiate the words $(ac)^\omega \in W_4$ and $(aac)^\omega \notin W_4$ from $s$. Let then $x, y \in \{a, c\}$ be such that $\mathcal{A}$ contains transitions $q \xrightarrow{x} p$ and $p \xrightarrow{y} q$.

Now, let us study the structure of the *b*-transitions. There are two possibilities:

(1) $s \xrightarrow{b} s$ **for some** $s \in \{q, p\}$: We suppose $s = q$ w.l.o.g. In this case, $\mathcal{A}$ does not differentiate between $(bxy)^\omega \notin W_4$ and $(bbxy)^\omega \in W_4$ from $q$.

(2) $q \xrightarrow{b} p$ **and** $p \xrightarrow{b} q$: In this case, $\mathcal{A}$ does not differentiate between $(byxbxy)^\omega \notin W_4$ and $(bbxy)^\omega \in W_4$.

We conclude that $\mathcal{A}$ cannot recognise $W_4$. $\square$

<figure><img src="image_29.png" /></figure>