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 [23, Corollary 1.1]. Therefore notions from this
paper indeed collapse with those from [24] 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 1) fails
when using the stronger definition of universality.

######  Proposition 5.8.

There exits a prefix-independent objective $W$ with $\varepsilon$-memory $\leq
2$ such that for all $m\geq 1$, there is a graph $G_{m}$ satisfying $W$ such
that any monotone graph satisfying $W$ and embedding $G_{m}$ has width $\geq
m$.

######  Proof 5.9.

Let $C=\\{a,b\\}$ and

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

For $m\geq 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 16. Note that it indeed satisfies $W$.

Figure 16: The graph $G_{m}$ from the proof of Proposition 5.8. As often, some
edges are omitted for clarity.

Let $(U,\leq)$ 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\leq i<j\leq m-1$ such that $\phi(i)$ and $\phi(j)$ are
comparable in $U$.

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

$\phi(i)\xrightarrow{a}\phi(j)\geq\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)\geq\phi(j)$ is dealt with symmetrically by constructing a path of
colouration $b^{\omega}\notin W$.

##  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 [24] 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 [24],
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}\ltimes W_{2}$ over $C=C_{1}\sqcup C_{2}$ by

$W_{1}\ltimes 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.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

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)\ltimes\mathrm{TL}(1)\ltimes\mathrm{TW}(2)\ltimes\dots\ltimes\mathrm{TL}(2h-1)\ltimes\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}.$

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

Given two partially ordered sets $(U_{1},\leq_{1})$ and $(U_{2},\leq_{2})$,
their _lexicographical product_ $\leq$ is defined over $U=U_{1}\times U_{2}$
by

$(u_{1},u_{2})\leq(u_{1}^{\prime},u_{2}^{\prime})\iff
u_{2}<u_{2}^{\prime}\text{ or }[u_{2}=u_{2}^{\prime}\text{ and }u_{1}\leq
u_{1}^{\prime}].$

If both $\leq_{1}$ and $\leq_{2}$ are well-founded, then so is their
lexicographical product $\leq$. The following simple property relates
antichains in $\leq_{1}$ and $\leq_{2}$ to those in their product.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

######  Lemma 6.1.

A set $A\subseteq U_{1}\times U_{2}$ defines an antichain in $\leq$ if and
only if its projection on $U_{2}$ is an antichain with respect to $\leq_{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 $\leq_{1}$. Thus, if $\mu_{1}$ and
$\mu_{2}$ are upper bounds to the size of antichains in $\leq_{1}$ and
$\leq_{2}$, then $\mu_{1}\mu_{2}$ is an upper bound to the size of antichains
in $\leq$.

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 17.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

Figure 17: Illustration of the lexicographical product of two ordered graphs.

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:

$\begin{array}[]{lcl}E(U)&=&\\{(u_{1},u_{2})\xrightarrow{c_{1}}(u_{1}^{\prime},u_{2}^{\prime})\mid
c_{1}\in C_{1}\text{ and }(u_{2}>_{2}u_{2}^{\prime}\text{ or
}[u_{2}=u_{2}^{\prime}\text{ and
}u_{1}\xrightarrow{c_{1}}u_{1}^{\prime}])\\}\\\
&&\cup\quad\\{(u_{1},u_{2})\xrightarrow{c_{2}}(u_{1}^{\prime},u_{2}^{\prime})\mid
c_{2}\in C_{2}\text{ and
}u_{2}\xrightarrow{c_{2}}u_{2}^{\prime}\\}.\end{array}$

We denote this product by $U=U_{1}\ltimes 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 6.3.

Let

$(v_{1},v_{2})\geq(u_{1},u_{2})\xrightarrow{c}(u_{1}^{\prime},u_{2}^{\prime})\geq(v_{1}^{\prime},v_{2}^{\prime})$

in $U$. There are two cases.

  * •

If $c\in C_{1}$, then again there are two cases.

    * –

If $u_{2}>u_{2}^{\prime}$, then we have $v_{2}\geq u_{2}>u_{2}^{\prime}\geq
v_{2}^{\prime}$ which concludes.

    * –

Otherwise we have $u_{2}=u_{2}^{\prime}$ and
$u_{1}\xrightarrow{c}u_{1}^{\prime}$. If $v_{2}>v_{2}^{\prime}$ we conclude
immediately. Otherwise, we have $v_{2}=v_{2}^{\prime}$ and $v_{1}\geq
u_{1}\xrightarrow{c}u_{1}^{\prime}\geq v_{1}^{\prime}$ and the result follows
from monotonicity in $U_{1}$.

  * •

If $c\in C_{2}$, then by definition, $u_{2}\xrightarrow{c}u_{2}^{\prime}$.
Since moreover it holds that $v_{2}\geq u_{2}$ and $u_{2}^{\prime}\geq
v_{2}^{\prime}$, we conclude thanks to monotonicity in $U_{2}$.

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

######  Theorem 2.

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}\ltimes U_{2}$ is
monotone and $(\kappa,W_{1}\ltimes W_{2})$-universal.

Combining with Theorems 1 and 2 together with Proposition 3.7 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}\ltimes 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 $\leq 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{array}[]{lclcl}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{array}$

By Corollary 6.4, since $\mathrm{TL}(a)$ and $\mathrm{TW}(a)$ are positional,
each of these four objectives has $\varepsilon$-memory $\leq m$. The first two
objectives have sometimes been called respectively
$W\land\mathrm{CoB\"{u}chi}(a)$ and $W\lor\mathrm{B\"{u}chi}(a)$ in the
literature, and it was known from the work of Kopcyński [18] 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 4.

The proof of Theorem 4 is similar to that of Ohlmann [24, Theorem 8.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},\leq_{1})$ and $(U_{2},\leq_{2})$
as in the statement of Theorem 4, 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 3.

The graph $U$ satisfies $W$.

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^{i}_{1},u^{i}_{2})$. 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\geq i_{0}$.

Then by definition of $C_{1}$-edges in $U$, it holds that

$u^{i_{0}}_{2}\geq_{2}u^{i_{0}+1}_{2}\geq_{2}u^{i_{0}+2}_{2}\geq_{2}\dots.$

Thus by well-foundedness of $\leq_{2}$, the $u^{i_{0}+i}_{2}$ are constant
after some point, say for $i\geq i_{1}$. Thus it holds that

$u^{i_{1}}_{1}\xrightarrow{c^{i_{1}}}u^{i_{1}+1}_{1}\xrightarrow{c^{i_{1}+1}}\dots$

is a path in $U_{1}$, and therefore $c^{i_{1}}c^{i_{1}+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}\geq
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)$ into according to colours of incoming edges, that is, we
let

$\displaystyle V_{2}=\\{t_{0}\\}\cup\\{t\in V(T)\mid\exists t^{\prime}\in
V(T)\text{ and }c_{2}\in C_{2}\text{ with }t^{\prime}\xrightarrow{c_{2}}t\in
E(T)\\}$ $\displaystyle\text{ and }\quad V_{1}=\\{t\in V(T)\mid\exists
t^{\prime}\in V(T)\text{ and }c_{1}\in C_{1}\text{ with
}t^{\prime}\xrightarrow{c_{1}}t\text{ in }E(T)\\}.$

Note that indeed we have $V(T)=V_{1}\sqcup V_{2}$. For each $t\in V(T))$, we
moreover define the $V_{2}$-ancestor of $t$, denoted $\mathrm{anc}_{2}(t)\in
V_{2}$, to be the closest ancestor of $t$ belonging to $V_{2}$, that is, the
unique $t^{\prime}\in V_{2}$ with a path of $C_{1}$-edges towards $t$ in $T$;
note that for $t\in T_{2}$ we have $(t)=t$.

We now define a $C_{2}$-pretree $T_{2}$ rooted at $t_{0}$ by contracting the
$C_{1}$-edges in $T_{2}$, formally we let $V(T_{2})=V_{2}$ and

$E(T_{2})=\\{t\xrightarrow{c_{2}}t^{\prime}\mid
t\overset{C_{1}^{*}c_{2}}{\rightsquigarrow}t^{\prime}\\}.$

######  Claim 4.

The $C_{2}$-pretree $T_{2}$ satisfies $W_{2}$.

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^{\prime}:t_{0}\xrightarrow{C_{1}^{*}c^{0}}t_{1}\xrightarrow{C_{1}^{*}c^{1}}\dots$

in $T$. Since $T$ satisfies $W$ and $\pi^{\prime}$ 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}$.

Since moreover $|T_{2}|\leq|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}(\mathrm{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
$\mathrm{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 5.

For any $u_{2}\in U_{2}$, it holds that $T_{1}^{u_{2}}$ satisfies $W_{1}$.

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).

Since moreover $|T_{1}^{u_{2}}|\leq|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}(\mathrm{anc}_{2}(v))$). The following claim concludes the
proof of Theorem 4.

######  Claim 6.

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

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^{\prime}\in E(T)$ with $c_{1}\in
C_{1}$. Then $t$ and $t^{\prime}$ have the same $2$-ancestor, and therefore
$t\xrightarrow{c_{1}}t^{\prime}$ is an edge in $T_{1}^{u_{2}}$ for
$u_{2}=\phi_{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^{\prime})\in
E(U_{1})$. Hence by definition of $U$, it indeed holds that
$\phi(t)\xrightarrow{c_{1}}\phi(t^{\prime})=(\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^{\prime}\in E(T)$ with $c_{2}\in
C_{2}$. Then $t^{\prime}\in V_{2}$. Let $t_{0}=\mathrm{anc}_{2}(v)$, and
observe that $t_{0}\xrightarrow{c_{2}}t^{\prime}\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^{\prime})\in E(U_{2})$ thus by
definition of $U$ we get that
$\phi(t)\xrightarrow{c_{2}}\phi(t^{\prime})=(u_{1},\phi_{2}(t_{0}))\xrightarrow{c_{2}}(u_{1}^{\prime},\phi_{2}(t))\in
E(U)$(regardless of $u_{1}$ and $u_{1}^{\prime}$).

This concludes the proof.

###  6.2 Combining games with unbounded finite memory

In this final section, we investigate properties of objectives which have
memory $<\aleph_{0}$. This means that for any game there is an optimal
strategy $\mathcal{S}$ such that for all vertices $v$, the amount of memory
used at $v$ (that is, the cardinality of $\pi_{\mathcal{S}}^{-1}(v)$) is
finite; however it may be that there is no uniform finite bound on the
$|\pi_{\mathcal{S}}^{-1}(v)|$’s, even when the game is fixed. An example of
such a game is discussed in Figure 18.

Figure 18: 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 finite unbounded memory. Since bi-boundedness objectives are
intersections of two positional [25] objectives (being bounded from above and
from below), our results in this section ensure that any game with a bi-
boundedness objective has optimal unbounded finite memory strategies.

Note that when applied to $\mu=\aleph_{0}$, since well-founded orders with
bounded antichains correspond to well-quasi-orders (wqo’s), Theorem 2 states
that the existence of universal monotone graphs which are wqo’s for a given
objective (or even, a valuation) entails $\varepsilon$-free memory
$<\aleph_{0}$. Unfortunately this is not a characterisation: Proposition 5.1
applied to $\mu=\aleph_{0}$ gives an objective with $\varepsilon$-free memory
$2<\aleph_{0}$ 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.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

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}^{\prime},u_{2}^{\prime})\iff[u_{1}\leq
u_{1}^{\prime}]\text{ and }[u_{2}\leq u_{2}^{\prime}].$

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 [12]) that, assuming well-foundedness, one may not go
from finite to infinite antichains.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

######  Lemma 6.5 (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}^{\prime},v_{2}^{\prime})\mid
v_{1}\xrightarrow{c}v_{1}^{\prime}\in E(G_{1})\text{ and
}v_{2}\xrightarrow{c}v_{2}^{\prime}\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.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

######  Lemma 6.6.

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 6.7.

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^{\prime}\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^{\prime})\in E(U_{i})$ and therefore by
definition of $U$, $\phi(t)\xrightarrow{c}\phi(t^{\prime})\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$.

Therefore, by combining Lemma 6.5 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 2, $W_{1}\cap W_{2}$ has memory
$<\aleph_{0}$. In particular, thanks to Theorem 1, we get the following weak
closure property.

######  Corollary 6.8.

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 $\varepsilon$-memory $<\aleph_{0}$ has
$\varepsilon$-free memory $<\aleph_{0}$.

The upper bound stated in the corollary is met: bi-boundedness objectives (see
Figure 18) gives an example where $W_{1}$ and $W_{2}$ are positional but
$W_{1}\cap W_{2}$ has $\varepsilon$-free memory exactly $\aleph_{0}$. Note
also that, thanks to Proposition 2.3, the hypothesis in the corollary can be
replaced by “$\varepsilon$-memory $<\aleph_{0}$”. Note moreover that the
corollary fails (bi-boundedness objectives are an example) if
“$\varepsilon$-free memory” is replaced by “$\varepsilon$-memory” in the
conclusion. Although our results fall short of implying such a strong closure
property, we may still state the following conjecture.

######  Conjecture 6.9.

Objectives with $\varepsilon$-free memory $<\aleph_{0}$ are closed under
intersection.

Finally, observe that if an objective has memory $<\aleph_{0}$, 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}\dots\in\\{-1,0,1\\}^{\omega}\mid\exists
k\in\mathbb{N},\sum_{i=0}^{k-1}w_{i}\leq-1\right\\}.$

Indeed, one can prove that this objective has finite memory over finite games,
however, Eve requires 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}$.

##  7 Conclusion

In this paper, we have extended Ohlmann’s work [24] 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 1 and 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 [10] and
Muller objectives [14]. 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.12).

The second kind of application discussed in the paper is the study of the
combinations of objectives. We have used our characterizations to bound the
memory requirements of finite lexicographical product of objectives (Section
6.1). We have also established intersections of objectives with finite
$\varepsilon$-memory always have finite $\varepsilon$-free memory. 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 5.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 [18]: are unions of prefix-independent positional
objectives positional? This conjecture has recently been disproved for finite
game graphs by Kozachinskiy [19], but it remains open for arbitrary game
graphs. We propose a generalisation of Kopczyński’s conjecture in the case of
$\varepsilon$-memory.

######  Conjecture 7.1.

Let $W_{1}\subseteq C^{\omega}$ and $W_{2}\subseteq C^{\omega}$ be two prefix-
independent objectives with $\varepsilon$-memory $\leq n_{1},n_{2}$,
respectively. Then $W_{1}\cup W_{2}$ has $\varepsilon$-memory $\leq
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. However, very little
is known about their memory requirements, and even about their positionality.
By now, thanks to recent work of Bouyer, Casares, Randour and Vandenhove [1],
which relies on Ohlmann’s characterisation, positionality is understood for
objectives recognised by deterministic Büchi automata.

Characterising positionality or memory requirements for other general classes
of $\omega$-regular objectives, such as those recognised by deterministic co-
Büchi automata or by deterministic automata of higher parity index remains an
open and challenging endeavour. 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
help progress in this direction.

## References

  * [1] Patricia Bouyer, Antonio Casares, Mickael Randour, and Pierre Vandenhove.  Half-positional objectives recognized by deterministic Büchi automata.  In CONCUR, volume 243, pages 20:1–20:18, 2022.  doi:10.4230/LIPIcs.CONCUR.2022.20.
  * [2] Patricia Bouyer, Stéphane Le Roux, Youssouf Oualhadj, Mickael Randour, and Pierre Vandenhove.  Games where you can play optimally with arena-independent finite memory.  In CONCUR, volume 171, pages 24:1–24:22, 2020.  doi:10.4230/LIPIcs.CONCUR.2020.24.
  * [3] Patricia Bouyer, Youssouf Oualhadj, Mickael Randour, and Pierre Vandenhove.  Arena-independent finite-memory determinacy in stochastic games.  In CONCUR, volume 203, pages 26:1–26:18, 2021.  doi:10.4230/LIPIcs.CONCUR.2021.26.
  * [4] Patricia Bouyer, Mickael Randour, and Pierre Vandenhove.  Characterizing omega-regularity through finite-memory determinacy of games on infinite graphs.  In STACS, volume 219, pages 16:1–16:16, 2022.  doi:10.4230/LIPIcs.STACS.2022.16.
  * [5] 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.
  * [6] 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.
  * [7] 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.
  * [8] Thomas Colcombet and Nathanaël Fijalkow.  Parity games and universal graphs.  CoRR, abs/1810.05106, 2018.  arXiv:1810.05106.
  * [9] 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.
  * [10] 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.
  * [11] 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.
  * [12] 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.
  * [13] Robert P. Dilworth.  A decomposition theorem for partially ordered sets.  Annals of Mathematics, 51(1):161–166, 1950.  doi:10.2307/1969503.
  * [14] 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.
  * [15] Hugo Gimbert and Wieslaw 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.
  * [16] Yuri Gurevich and Leo Harrington.  Trees, automata, and games.  In STOC, page 60–65, 1982.  doi:10.1145/800070.802177.
  * [17] Florian Horn.  Random Games.  PhD thesis, Université Denis Diderot - Paris 7 & Rheinisch-Westfälische Technische Hochschule Aachen, 2008.
  * [18] Eryk Kopczyński.  Half-positional Determinacy of Infinite Games.  PhD thesis, Warsaw University, 2008.
  * [19] Alexander Kozachinskiy.  Energy games over totally ordered groups.  CoRR, abs/2205.04508, 2022.  doi:10.48550/arXiv.2205.04508.
  * [20] Alexander Kozachinskiy.  Infinite separation between general and chromatic memory.  CoRR, abs/2208.02691, 2022.  doi:10.48550/arXiv.2208.02691.
  * [21] Alexander Kozachinskiy.  State complexity of chromatic memory in infinite-duration games.  CoRR, abs/2201.09297, 2022.  arXiv:2201.09297.
  * [22] Jean-Louis Krivine.  Introduction to Axiomatic Set Theory.  Dordrecht, Netherland: Springer, 1971.
  * [23] Pierre Ohlmann.  Monotonic graphs for parity and mean-payoff games.  PhD thesis, Université de Paris, 2021.
  * [24] Pierre Ohlmann.  Characterizing positionality in games of infinite duration over infinite graphs.  In LICS, pages 22:1–22:12, 2022.  doi:10.1145/3531130.3532418.
  * [25] Pierre Ohlmann.  Characterizing positionality in games of infinite duration over infinite graphs.  CoRR, abs/2205.04309, 2022.  doi:10.48550/arXiv.2205.04309.
  * [26] Micha A. Perles.  On Dilworth’s theorem in the infinite case.  Israel Journal of Mathematics, 1(1):108–109, 1963.  doi:10.1007/BF02759806.
  * [27] 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 [22].

###  A.1 Orders and preorders

A binary relation $\leq$ over a set $A$ is a _preorder_ (resp. _strict
preorder_) if it is reflexive ($\forall x,x\leq x$) (resp. it is anti-
reflexive, $\forall x,x\nleq x$) and transitive ($x\leq y$ and $y\leq z$
implies $x\leq z$). Given a preorder $\leq$, we note $<$ the strict preorder
defined by: $x<y\text{ if }x\leq y\text{ and }x\neq y$. A preorder (resp.
_strict preorder_) is an _order_ (resp. _strict order_) if it is antisymmetric
($x\leq y$ and $y\leq x$ implies $x=y$). A _(pre)ordered set_ $(A,\leq)$ is a
set together with a (pre)order relation.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

We say that two elements $x,y$ of a preordered set are _comparable_ if $x\leq
y$ or $y\leq 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_.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

A _chain_ of an ordered set $(A,\leq)$ is a subset $S\subseteq A$ whose
elements are pairwise comparable. An _antichain_ of an ordered set $(A,\leq)$
is a subset $S\subseteq A$ whose elements are pairwise incomparable ($\forall
x,y\in S$, $x\nleq y$ and $y\nleq x$).

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

Let $(A,\leq)$ be an ordered set. A _maximal (resp. minimal) element_ of $S$
is an element $m\in S$ such that $\forall x\in S$, $m\leq x$ (resp. $x\leq m$)
implies $m\leq x$ (resp. $x\leq m$). An element $a\in A$ is a _supremum (resp.
infimum) of $S$_ if $\forall x\in S,x\leq a$ (resp. $\forall x\in S,a\leq x$
and for any other $b\in A$ with this property $a\leq b$ (resp. $b\leq 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 call
a _maximum_ (resp. _minimum_).

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

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.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

A partially preordered set $(A,\leq)$ 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,\leq)$ 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).

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

Two ordered sets $(A,\leq_{1})$, $(B,\leq_{2})$ are _order isomorphic_ if
there exists an order preserving bijection between them, that is, a bijection
$\phi\colon A\to B$ such that for all $x,y\in A$, $x\leq_{1}y$ implies
$\phi(x)\leq_{2}\phi(y)$ and for all $x,y\in B$ $x\leq_{2}y$ implies
$\phi^{-1}(x)\leq_{1}\phi^{-1}(y)$

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

######  Theorem 6 (Well-ordering principle).

Any set admits a well-ordering.

######  Theorem 6 (Dilworth’s Theorem [13]).

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. 1.

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

  2. 2.

If $x\in\alpha$, then $x\subsetneq\alpha$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

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.1 (_Transfinite recursion_).

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

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

Two sets are said to be _equinumerous_ if there exits 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.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

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 $\immediate|A|$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

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
${\immediate\immediate\immediate\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 Chromatic memory of $C^{*}a^{n}C^{\omega}$

In Section 4.1 we studied the topologically open objective

$W_{3}=C^{*}a^{n}C^{\omega}\text{ over }C=\\{a,b\\}.$

We showed that its $\varepsilon$-memory is exactly $2$ and that its
$\varepsilon$-chromatic memory is $\leq n$ by providing an
$\varepsilon$-separated chromatic universal graph. We claimed that this is
optimal, that is, that its $\varepsilon$-chromatic memory is exactly $n$; this
is proved in this section.

By [18, Proposition 8.9] (see also Remark 3.1), it suffices to show that there
is no small arena-independent memory: if $M$ is a set together with an update
function $\delta\colon M\times C\to M$ such that in any $C$-game with
objective $W_{3}$ Eve can reach its value with product strategies over $M$
(consistent with $\delta$), then $|M|\geq n$. We moreover assume that there is
a memory state $m_{0}\in M$ such that for any product strategy the initial
vertex is of the form $s_{0}=(v_{0},m_{0})$. We will show how to get rid of
this assumption at the end of the proof.

Let $M$ be a set with an update function $\delta\colon M\times C\to M$ of size
$|M|<n$. We show that there is a $C$-game where Eve can win, but not using a
product strategy over $M$. We denote $\delta\colon M\times C^{*}\to M$ the
extension of $\delta$ to finite words defined naturally by induction.

######  Claim 7.

There is a memory state $m^{\star}\in M$, numbers $r,s,t,k\in\mathbb{N}$,
$k,t\geq 1$ and words $w_{0},w_{1}\in C^{*}$ either empty or ending by $b$ and
not containing $a^{n}$ as a factor such that:

  * •

$\delta^{*}(m_{0},w_{0}a^{r})=m^{\star}$,

  * •

$\delta^{*}(m^{\star},a^{t})=m^{\star}$,

  * •

$\delta^{*}(m^{\star},bw_{1}a^{s})=m^{\star}$,

  * •

$r+t<n$,

  * •

$s+kt<n$,

  * •

$s+(k+1)t\geq n$.

We depict the situation in Figure19.

Figure 19: Cycles over the states of a memory structure for $W_{3}$.

Let us prove the result assuming Claim 7. Consider the game $\mathcal{G}$ from
Figure 20. Eve can win this game, since she can produce the word
$w_{0}a^{r}(bw_{1}a^{s}a^{kt}a^{t}bw_{1}a^{s})^{\omega}$ by alternating the
two cycles from vertex $v$. This word contains the factor $a^{s}a^{kt}a^{t}$,
so it contains $a^{n}$ since $s+(k+1)t\geq n$.

However, there is no winning product strategy over $M$ with update function
$\delta$. Indeed, let $(S,\pi_{\mathcal{S}},s_{0})$ be such a strategy; we
have $s_{0}=(v_{0},m_{0})$ and $(v,m)\xrightarrow{c}(v^{\prime},m^{\prime})\in
E(S)$ implies $m^{\prime}=\delta(m,c)$. Since $S$ does not have sinks and
$\pi_{S}$ is a morphism, $S$ contains a path of the form
$(v_{0},m_{0})\mathrel{\leavevmode\hbox to17.92pt{\vbox
to10.57pt{\pgfpicture\makeatletter\hbox{\hskip 8.96057pt\lower-5.8347pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-6.4078pt}{-1.29306pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\scriptstyle
w_{0}a^{r}$}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} { {}}{}{{}}{}{{}} {}{}
{}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}} {{{{}{}{{}} }}{{}} }{{{{}{}{{}}
}}{{}}}{{{{}{}{{}} }}{{}}{{}}} {{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {}
}{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {}
}{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {{}} }
{{{{}{}{{}} }}{{}}{{}}} {}{{
{\pgfsys@beginscope\pgfsys@setdash{}{0.0pt}\pgfsys@roundjoin{} {}{}{} {}{}{}
{}{}{}
\pgfsys@moveto{0.79999pt}{0.0pt}\pgfsys@curveto{-0.2pt}{0.2pt}{-1.19998pt}{0.59999pt}{-2.39996pt}{1.29997pt}\pgfsys@curveto{-1.19998pt}{0.4pt}{-1.19998pt}{-0.4pt}{-2.39996pt}{-1.29997pt}\pgfsys@curveto{-1.19998pt}{-0.59999pt}{-0.2pt}{-0.2pt}{0.79999pt}{0.0pt}\pgfsys@closepath\pgfsys@fillstroke\pgfsys@endscope}}
}{}{}{{}}\pgfsys@moveto{7.76059pt}{-4.93471pt}\pgfsys@lineto{4.76057pt}{-4.93471pt}\pgfsys@lineto{3.907pt}{-5.6347pt}\pgfsys@lineto{2.19983pt}{-4.23471pt}\pgfsys@lineto{0.49266pt}{-5.6347pt}\pgfsys@lineto{-1.21451pt}{-4.23471pt}\pgfsys@lineto{-2.92168pt}{-5.6347pt}\pgfsys@lineto{-4.62885pt}{-4.23471pt}\pgfsys@lineto{-6.33601pt}{-5.6347pt}\pgfsys@lineto{-8.76057pt}{-4.93471pt}\pgfsys@lineto{-8.76057pt}{-4.93471pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{7.76059pt}{-4.93471pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{}{{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}(v,m^{\star})$ and it
contains one of the two following loops over $(v,m^{\star})$:

$(v,m^{\star})\mathrel{\leavevmode\hbox to26.03pt{\vbox
to11.56pt{\pgfpicture\makeatletter\hbox{\hskip 13.01457pt\lower-6.32774pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-10.4618pt}{-1.7861pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\scriptstyle
a^{t}bw_{1}a^{s}$}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} { {}}{}{{}}{}{{}} {}{}
{}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}} {{{{}{}{{}} }}{{}} }{{{{}{}{{}}
}}{{}}}{{{{}{}{{}} }}{{}}{{}}} {{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {}
}{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {}
}{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {}
}{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {}
}{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {{}} } {{{{}{}{{}} }}{{}}{{}}}
{}{}{}{}{{}}\pgfsys@moveto{11.81459pt}{-5.42775pt}\pgfsys@lineto{8.81458pt}{-5.42775pt}\pgfsys@lineto{7.961pt}{-6.12775pt}\pgfsys@lineto{6.25383pt}{-4.72775pt}\pgfsys@lineto{4.54666pt}{-6.12775pt}\pgfsys@lineto{2.8395pt}{-4.72775pt}\pgfsys@lineto{1.13232pt}{-6.12775pt}\pgfsys@lineto{-0.57484pt}{-4.72775pt}\pgfsys@lineto{-2.28201pt}{-6.12775pt}\pgfsys@lineto{-3.98918pt}{-4.72775pt}\pgfsys@lineto{-5.69635pt}{-6.12775pt}\pgfsys@lineto{-7.40352pt}{-4.72775pt}\pgfsys@lineto{-9.11069pt}{-6.12775pt}\pgfsys@lineto{-10.81786pt}{-4.72775pt}\pgfsys@lineto{-12.81458pt}{-5.42775pt}\pgfsys@lineto{-12.81458pt}{-5.42775pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{11.81459pt}{-5.42775pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{}{{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}(v,m^{\star})\quad\text{
or }\quad(v,m^{\star})\mathrel{\leavevmode\hbox to28.24pt{\vbox
to11.56pt{\pgfpicture\makeatletter\hbox{\hskip 14.11873pt\lower-6.32774pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-11.56596pt}{-1.7861pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\scriptstyle
bw_{1}a^{s}a^{kt}$}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} { {}}{}{{}}{}{{}} {}{}
{}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}} {{{{}{}{{}} }}{{}} }{{{{}{}{{}}
}}{{}}}{{{{}{}{{}} }}{{}}{{}}} {{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {}
}{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {}
}{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {}
}{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {}
}{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {} }{{{{}{}{{}} }}{{}} {{}} }
{{{{}{}{{}} }}{{}}{{}}}
{}{}{}{}{{}}\pgfsys@moveto{12.91875pt}{-5.42775pt}\pgfsys@lineto{9.91873pt}{-5.42775pt}\pgfsys@lineto{9.06516pt}{-6.12775pt}\pgfsys@lineto{7.35799pt}{-4.72775pt}\pgfsys@lineto{5.65082pt}{-6.12775pt}\pgfsys@lineto{3.94365pt}{-4.72775pt}\pgfsys@lineto{2.23648pt}{-6.12775pt}\pgfsys@lineto{0.52931pt}{-4.72775pt}\pgfsys@lineto{-1.17786pt}{-6.12775pt}\pgfsys@lineto{-2.88503pt}{-4.72775pt}\pgfsys@lineto{-4.5922pt}{-6.12775pt}\pgfsys@lineto{-6.29936pt}{-4.72775pt}\pgfsys@lineto{-8.00653pt}{-6.12775pt}\pgfsys@lineto{-9.7137pt}{-4.72775pt}\pgfsys@lineto{-11.42087pt}{-6.12775pt}\pgfsys@lineto{-13.91873pt}{-5.42775pt}\pgfsys@lineto{-13.91873pt}{-5.42775pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{12.91875pt}{-5.42775pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}{}{{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}(v,m^{\star}).$

Therefore, $\mathcal{S}$ contains a losing path: in the first case, the path
labelled by $w_{0}a^{r}(a^{t}bw_{1}a^{s})^{\omega}$ is losing; whereas in the
second case the path $w_{0}a^{r}(bw_{1}a^{s}a^{kt})^{\omega}$ is losing, since
$r+t<n$ and $s+kt<n$. This concludes the proof.

Figure 20: Game where Eve cannot win using a chromatic product strategy over
$M$.

######  Proof B.1 (Proof of Claim 7).

We can see $(M,\delta)$ as a $C$-graph $G_{M}$ given by $V(G_{M})=M$ and
$E(G_{M})=\\{m\xrightarrow{c}m^{\prime}\mid\delta(m,c)=m^{\prime}\\}$. We
remark that each vertex of $G_{M}$ has exactly two outgoing edges, one
labelled by $a$ and the other by $b$.

First, let $G^{\prime}$ be the restriction of $G_{M}$ to a final strongly
connected component reachable from $m_{0}$. Then consider a cycle $V_{a}$
labelled by $a$’s in $G^{\prime}$ and let $t=|V_{a}|$. Let $w$ be a word of
minimal length from $m_{0}$ to this cycle. We let $r_{1}$ maximal such that
$a^{r}$ is a suffix of $w$. We note that $r_{1}<n-t$. We let
$m_{1}=\delta^{*}(m_{0},w)$, and for $1\leq i\leq t-1$,
$m_{i+1}=\delta(m_{i},w)\in V_{a}$. Let $m_{i}^{\prime}=\delta(m_{i},b)$ for
$m_{i}\in V_{a}$, and let $w_{i}^{\prime}$ be a word labelling a simple path
from $m_{i}^{\prime}$ to the cycle $V_{a}$. Since (apart from its endpoint),
such a path is contained in $M\setminus V_{a}$, which has size $<n-t$, it
holds that $|w^{\prime}_{i}|\leq n-t$ and in particular it cannot contain the
factor $a^{n}$; let us write

$w_{i}^{\prime}=w_{i}^{\prime\prime}a^{l_{i}}$

with $l_{i}<n-t$ and $w_{i}^{\prime\prime}$ either empty or ending by $b$.

Consider the graph $\tilde{G}$ over $V(\tilde{G})=V_{a}=\\{1,\dots,t\\}$ given
by

$E(\tilde{G})=\\{m_{i}\rightarrow m_{j}\mid
m_{i}\overset{bw_{i}^{\prime}}{\rightsquigarrow}m_{j}\text{ in }G\\}.$

The graph $\tilde{G}$ has no sink (because $V_{a}$ is a final SCC): let
$m^{\star}\in V_{a}$ be the first vertex in a cycle in $\tilde{G}$ reachable
(in $\tilde{G}$) from $m_{1}$, that is, we have paths of the form

$m_{1}\overset{bw_{1}^{\prime}}{\rightsquigarrow}m_{i_{1}}\overset{}{\rightsquigarrow}\cdots\overset{bw_{x}^{\prime}}{\rightsquigarrow}m^{\star}\quad\text{
and }\quad
m^{\star}\overset{bw_{j}^{\prime}}{\rightsquigarrow}m_{j_{1}}\overset{}{\rightsquigarrow}\cdots\overset{bw_{y}^{\prime}}{\rightsquigarrow}m^{\star}$

in $G$.

Finally, concatenating $w$ with the path from $m_{1}$ to $m^{\star}$ we obtain
a word labelling a path from $m_{0}$ to $m^{\star}$ that might end by a
sequence of $a$’s. We let this word be $w_{0}a^{r}$, with $w_{0}$ either empty
or ending by $b$. We remark that $r=r_{1}$ if $m^{\star}=m_{1}$ and $r=l_{x}$
on the contrary; in both cases $r<n-t$. The word labelling the cycle over
$m^{\star}$ built above is of the form $bw_{1}a^{s}$ with $w_{1}$ either empty
or ending with $b$ and not containing the factor $a^{n}$. It also holds that
$s<n-t$. We let $k\geq 1$ be the greatest integer such that $s+kt<n$. This
way, all requirements from the statement of the claim are met.

Finally, we explain how we can get rid of the hypothesis that there is an
initial memory state $m_{0}\in M$ such that for any product strategy the
initial vertex is of the form $s_{0}=(v_{0},m_{0})$. We perform the
construction above taking as initial memory state each $m\in M$. For each one,
we obtain a different game $\mathcal{G}_{m}$. We then consider the disjoint
union of these games and add an initial vertex $v_{\mathrm{Adam}}$ controlled
by Adam and $\varepsilon$-transitions from this vertex to the initial vertices
of the games $\mathcal{G}_{m}$. Therefore, for any product strategy
$\mathcal{S}$ over $M$, $|M|<n$, with initial vertex $(v_{0},m)$, Eve cannot
force a victory if Adam chooses to play in the game $\mathcal{G}_{m}$.