# Activity and mood-based routing for autonomous vehicles

Ankit Kariryaa

Tony Veale

Johannes Schöning

University of Bremen  Bremen, Germany<EMAIL_ADDRESS>University
College Dublin  Dublin, Ireland<EMAIL_ADDRESS>University of Bremen
Bremen, Germany<EMAIL_ADDRESS>
###### Abstract

A significant amount of our daily lives is dedicated to driving, leading to an
unavoidable exposure to driving-related stress. The rise of autonomous
vehicles will likely lessen the extent of this stress and enhance the routine
traveling experience. Yet, no matter how diverse they may be, current routing
criteria are limited to considering only the passive preferences of a
vehicle’s users. Thus, to enhance the overall driving experience in autonomous
vehicles, we advocate here for the diversification of routing criteria, by
additionally emphasizing activity- and mood-based requirements.

###### keywords:

Routing preference; Autonomous vehicles;

###### category:

H.5.m Information interfaces and presentation (e.g., HCI) Miscellaneous

##  1 Introduction & Motivation

A significant amount of our time is typically spent driving. For example, in
2014, 83.4% of total inland travel in the EU-28 was carried out in passenger
cars [5]. The negative effects of driving-related stress are well known [8],
and while autonomous vehicles are expected to remove some of these stressors,
such as e.g., the behavior of other drivers, the cognitive (over)load of
driving and other ergonomic factors, other external stressors, such as e.g.
environmental conditions, traffic congestion, and peripheral noise, are
independent of the vehicles themselves. To create a pleasant driving
experience and to improve a user’s interactions with an autonomous vehicle, we
believe users should be given the possibility to limit the influence of
external stressors. The related literature provides a large body of work on
criteria that optimize route-finding by distance, time, safety, simplicity,
efficiency and even scenery and other aesthetic preferences. We propose here
the enhancement of route-finding by activity and mood to improve the user’s
overall experience (and enjoyment) of travel in an autonomous vehicle.

##  2 Related work

A plethora of routing techniques supplement the most frequently used _fastest_
and _shortest_ route criteria. Based on the seminal work of Golledge in 1995
[7], Johnson et al. [9] categorizes these alternative routing techniques into
the _positive_ , _negative_ , _topological_ and _personalized_. The _positive_
category encompasses routes that are the most appealing or attractive. One
such technique is described by Runge et al. [15]. It is capable of generating
scenic routes via a classification of Google Street View images. Similarly,
Ali et al. [4] present an exploration-based route planner that learns from the
routes commonly taken by photographers. As a result, it generates
aesthetically-pleasing routes for city exploration and/or photography
sessions. Routes that include the least number of unfavorable or adverse
conditions to a particular user are classified as _negative_ routes, not
because the routes themselves are negative but because routing decisions are
made on the basis of discernible negatives. Shah et al. [16] demonstrated an
algorithm for generating safe routes, deduced from the reported levels of
crime in any given locality. Li et al. [12] created a routing service to be
used in cases of natural and man-made disasters. It first optimizes on
measures of survivability, and only then on travel time. Topological routes
give higher preference to factors such as simplicity or efficiency. Duckham
and Kulik [3] proposed a routing algorithm for simple routes that are easy to
describe and execute, while Ganti et al. [6] presented a fuel-efficient
routing algorithm. Among all approaches to routing, only personalized routes
take into account the preferences of individual users. Letchner et al. [11]
introduced the concept of an _individual inefficiency ratio_ (r) – which is
the degree to which a particular user deviates from the fastest route – to
fulfil personal preferences. It is based upon a large dataset of personal GPS
traces. This technique suggests routes by optimizing for the preferred ratio
“r” of the user. Delling et al. [2] proposed a routing algorithm that creates
routes based upon a user’s preferences for speed level, type of road, and
number and type of turns. While there has been extensive research into simple
routing strategies, as well as recent research into personalized routing, we
argue that the diverse needs of users cannot be satisfied with routing
techniques that exploit only the passive preferences of the user. Users of
non-autonomous vehicles can always optimize the suggested route based upon
their current needs, but such interventions become problematic in the context
of autonomous vehicles where active control is passed from the user to the
vehicle itself. Hence, we propose a routing approach that considers these
active elements and improves upon them.

##  3 Activity and mood-based routing

Research in route planning with individualized preferences shows that users
prefer different routes in different conditions [2, 11]. However, little has
been done to integrate the mood and activity of the user in the driving
preferences, that can play a crucial role in the overall driving experience.
Indeed, there is an even greater potential to incorporate the mood and
activity of a non-driving user of an autonomous vehicle into routing
preferences. While some of these preferences may be static – such as avoiding
areas of extreme weather or natural/social hazard – we argue that many other
preferences are dynamic, and in many cases, users can articulate their
requirements explicitly (e.g., the goal of reaching a destination in the
shortest time). However, in some cases a requirement cannot be mapped onto a
mathematical function that can then form the basis of optimization. The
_circumplex model_ of affect [14] maps human emotions onto a valence and
activation scale (see Fig. 1). Since different emotions are best suited to
certain activities (as was demonstrated by [10]), our goal for an empathic
autonomous vehicle is to alter the user’s mood to match the desired activity.
Here, we discuss some scenarios where activity- and mood-based routing will be
required.

Uplifting routes: Picard’s experiments (see [13]) have demonstrated the
crucial role of affect in human perception and cognition, as well as its
influence on such tasks as learning and decision-making. If a user experiences
an unpleasant emotion while driving, one which the user would like to alter,
the route itself can foster this change (see Fig. 1). For instance, the route
may change to visit places with associated personal value, such as the user’s
favorite restaurant, lively centers of public performance, or places of
natural beauty, in order to nurture more pleasant emotions. A scenic route can
be chosen so as to maximize the effect of surroundings and to highlight
ambient environmental conditions, such as e.g. a sunset.

Sleep-aiding routes: If the user of an autonomous vehicle wishes to sleep
during a journey, then the route preference can be optimized for the lowest
level of noise and the lowest amount of other road-related disturbances, e.g.
a route with the fewest turns, ensuring a smooth and continuous drive. It may
also factor in additional factors such as the sleep pattern and the required
sleep time of the user to promote a satisfying sleep.

Figure 1: The route preference can be adapted to drive the emotions according
to the requirement. Based upon the graphical circumplex model of affect in
[14].

Movie routes: If the users are watching a movie, then the route and speed of
an autonomous vehicle can be varied to match the duration of the movie. It can
also be chosen to suit its theme and to minimize environmental disturbances,
e.g. at night a country road can be given a higher preference in order to
minimize outer light disturbances. In certain cases, it may also be possible
to route through locations relevant to (or analogous to) scenes in the movie,
at times that match the timing of scenes in the movie, to further enhancing
the experience.

Educational routes: The autonomous vehicle can also propose routes based upon
the educational needs of the users. For example, a route can pass through
important areas and landmarks to familiarize users with the history of an
area. A route can also follow historical events, such as the course taken by
an important procession or march, to give a deep insight into the locality.
The route can also be chosen based upon the needs of a specific group, e.g. it
can include farms, parks, museums or galleries.

##  4 Discussion and future works

To enhance the user experience of autonomous vehicles, we have proposed new
routing criteria, including both the current activity/goal and mood of the
user, that should be taken into account when selecting the “best” route to a
user’s destination. These dynamic factors will diversify the route-finding
process and reduce the influence of hidden externalities.

Subsequently, an archive of chosen routes for a particular user can be used as
a basis for engaging user interaction, by including ideas from both the user
and the system. A creative route-finding system might come up with creative
new types of route, such as routes whose road-names spell the name of a known
person, or routes comprising the oldest or most historical roads, or routes
whose road-names provide the answers to riddles and quiz questions. Likewise,
a system may creatively choose a route based upon the plot of novel or a TV-
show/movie (e.g. _Game of Thrones_) that was filmed in or, set in, the
locality, and entertain the user with insights about both the plot and the
surrounding area. A creative system may also engage with the user in novel
ways, for example, by generating a route that passes through the largest
number of a certain type of building or establishment (e.g. bookshops, bars,
restaurants) and play a game with users by asking them to keep track of the
such establishments. In fact, a creative route-finding system should serve
many of the same functions as a creative travel-companion, one that possesses
much more than a map and an eye for traffic.

##  5 Acknowledgements

We would like to thank Nicolas Autzen and Tetiana Gren for valuable discussion
on the topic. This work was supported by the Volkswagen Foundation through a
Lichtenberg professorship.

## References

  * [1]
  * [2] Daniel Delling, Andrew V. Goldberg, Moises Goldszmidt, John Krumm, Kunal Talwar, and Renato F. Werneck. 2015.  Navigation Made Personal: Inferring Driving Preferences from GPS Traces. In Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL ’15). ACM, New York, NY, USA, Article 31, 9 pages.  DOI:http://dx.doi.org/10.1145/2820783.2820808
  * [3] Matt Duckham and Lars Kulik. 2003.  Simplest paths: automated route selection for navigation. In International Conference on Spatial Information Theory. Springer, 169–185.
  * [4] Abdallah El Ali, Sicco NA Van Sas, and Frank Nack. 2013.  Photographer paths: sequence alignment of geotagged photos for exploration-based route planning. In Proceedings of the 2013 conference on Computer supported cooperative work. ACM, 985–994.
  * [5] Eutostat. 2014.  Passenger transport statistics.  (2014).  http://ec.europa.eu/eurostat/statistics-explained/index.php/Passenger_transport_statistics
  * [6] Raghu K. Ganti, Nam Pham, Hossein Ahmadi, Saurabh Nangia, and Tarek F. Abdelzaher. 2010.  GreenGPS: A Participatory Sensing Fuel-efficient Maps Application. In Proceedings of the 8th International Conference on Mobile Systems, Applications, and Services (MobiSys ’10). ACM, New York, NY, USA, 151–164.  DOI:http://dx.doi.org/10.1145/1814433.1814450
  * [7] Reginald G Golledge. 1995.  Defining the criteria used in path selection.  University of California Transportation Center (1995).
  * [8] E Gulian, AI Glendon, G Matthews, DR Davies, and LM Debney. 1990.  The stress of driving: A diary study.  Work & Stress 4, 1 (1990), 7–16.
  * [9] Isaac Johnson, Jessica Henderson, Caitlin Perry, Johannes Schöning, and Brent Hecht.  Beautiful…but at What Cost? An Examination of Externalities in Geographic Vehicle Routing. In Submitted to UbiComp ’17: Proceedings of the 2017 ACM International Joint Conference on Pervasive and Ubiquitous Computing.
  * [10] Ashish Kapoor, Selene Mota, Rosalind W Picard, and others. 2001.  Towards a learning companion that recognizes affect. In AAAI Fall symposium. 2–4.
  * [11] Julia Letchner, John Krumm, and Eric Horvitz. 2006.  Trip router with individualized preferences (trip): Incorporating personalization into route planning. In Proceedings of the National Conference on Artificial Intelligence, Vol. 21. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 1795.
  * [12] YiRu Li, Sarah George, Craig Apfelbeck, Abdeltawab M. Hendawi, David Hazel, Ankur Teredesai, and Mohamed Ali. 2014.  Routing Service with Real World Severe Weather. In Proceedings of the 22Nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL ’14). ACM, New York, NY, USA, 585–588.  DOI:http://dx.doi.org/10.1145/2666310.2666375
  * [13] Rosalind W Picard and Roalind Picard. 1997.  Affective computing. Vol. 252.  MIT press Cambridge.
  * [14] J. Posner, J. A. Russell, and B. S. Peterson. 2005.  The circumplex model of affect: an integrative approach to affective neuroscience, cognitive development, and psychopathology.  Dev. Psychopathol. 17, 3 (2005), 715–734.
  * [15] Nina Runge, Pavel Samsonov, Donald Degraen, and Johannes Schöning. 2016.  No more autobahn!: Scenic route generation using googles street view. In Proceedings of the 21st International Conference on Intelligent User Interfaces. ACM, 147–151.
  * [16] Sumit Shah, Fenye Bao, Chang-Tien Lu, and Ing-Ray Chen. 2011.  CROWDSAFE: Crowd Sourcing of Crime Incidents and Safe Routing on Mobile Devices. In Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS ’11). ACM, New York, NY, USA, 521–524.  DOI:http://dx.doi.org/10.1145/2093973.2094064


# Infinite separation between general and chromatic memory

Alexander Kozachinskiy111The author is funded by ANID - Millennium Science
Initiative Program - Code ICN17002, and the National Center for Artificial
Intelligence CENIA FB210017, Basal ANID.
IMFD & CENIA, Chile
<EMAIL_ADDRESS>
###### Abstract

In this paper, we construct a winning condition $W$ over a finite set of
colors such that, first, every finite arena has a strategy with 2 states of
general memory which is optimal w.r.t. $W$, and second, there exists no $k$
such that every finite arena has a strategy with $k$ states of chromatic
memory which is optimal w.r.t. $W$.

##  1 Introduction

Memory requirements for games on graphs have been studied for decades.
Initially, these studies were motivated by applications to automata theory and
the decidability of logical theories. For example, the memoryless determinacy
of parity games is a key ingredient for the complementation of tree automata
and leads to the decidability of the monadic second-order theory of trees
[15]. Recently, games on graphs have become an important tool in reactive
synthesis [1]. They serve there as a model of the interaction between a
reactive system and the environment. One question studied in games on graphs
is which winning conditions admit “simple” winning strategies. The prevailing
measure of the complexity of strategies in the literature is memory. In this
note, we study two kinds of memory – _general_ (a.k.a.  _chaotic_) memory and
_chromatic_ memory. The relationship between them was first addressed in the
Ph.D. thesis of Kopczyński [12], followed by several recent works [3, 6, 7].

We focus on deterministic games, infinite-duration and turn-based. We call our
players Protagonist and Antagonist. They play over a finite222There are papers
that study these games over infinite graphs, but in this note we only work
with finite graphs. directed graph called an _arena_. Its set of nodes has to
be partitioned into ones controlled by Protagonist and ones controlled by
Antagonist. Players move a token over the nodes of the graph along its edges.
In each turn, the token is moved by the player controlling the current node.

After infinitely many turns, this process produces an infinite path in our
graph. A _winning condition_ is a set of infinite paths that are winning for
Protagonist. In the literature, a standard way of defining winning conditions
assumes that arenas are edge-colored by elements of some set of colors $C$.
Then any subset $W\subseteq C^{\omega}$ is associated with a winning
condition, consisting of all infinite paths whose sequence of colors belongs
to $W$.

In this paper, we seek simple winning strategies of Protagonist, while the
complexity of Antagonist’s strategies is mostly irrelevant to us. Such
asymmetry is motivated by reactive synthesis, where Protagonist represents a
system and Antagonist represents the environment. Now, the main measure of the
complexity of Protagonist’s strategies for us is memory. Qualitatively, we
distinguish between _finite-memory_ strategies and _infinite-memory_
strategies. In turn, among finite-memory strategies, we prefer those that have
fewer states of memory.

Finite-memory strategies are defined through so-called _memory structures_.
Intuitively, a memory structure plays the role of a “hard disk” of a strategy.
Formally, a _general_ memory structure $\mathcal{M}$ is a deterministic finite
automaton whose input alphabet is the set of edges of an arena. During the
game, edges over which the token moves are fed to $\mathcal{M}$ one by one.
Correspondingly, the state of $\mathcal{M}$ is updated after each move. Now, a
strategy _built on top of a memory structure_ $\mathcal{M}$ (or simply an
$\mathcal{M}$-strategy) is a strategy whose moves at any moment depend solely
on two things: first, the current arena node, and second, the current state of
$\mathcal{M}$. A strategy is finite-memory if it can be built on top of some
memory structure. More precisely, if this memory structure has $k$ states,
then strategies built on top of it are strategies _with $k$ states of general
memory_. Of course, some strategies cannot be built on top of any memory
structure. Such strategies are infinite-memory strategies.

We also consider a special class of general memory structures called
_chromatic_ memory structures. A memory structure is chromatic if its
transition function does not distinguish edges of the same color. In other
words, chromatic memory structures only reads colors of edges that are fed
into them. Alternatively, a chromatic memory structure can be viewed as a
finite automaton whose input alphabet is not the set of edges, but the set of
colors. Correspondingly, strategies that are built on top of a chromatic
memory structure with $k$ states are called strategies with _$k$ states of
chromatic memory_.

### Around a Kopczyński’s question

Complexity of strategies brings us to complexity of winning conditions. For a
given winning condition, we want to determine the minimal amount of memory
which is sufficient to win whenever it is possible to win. More specifically,
the general memory complexity of a winning condition $W$, denoted by
$\mathsf{GenMem}(W)$, is the minimal $k\in\mathbb{N}$ such that in every arena
there exists a Protagonist’s strategy $S$ with $k$ states of general memory
which is optimal w.r.t. $W$. If no such $k$ exists, we set
$\mathsf{GenMem}(W)=+\infty$. Now, “$S$ is optimal w.r.t. $W$” means that
there exists no node $v$ such that some Protagonist’s strategy is winning from
$v$ w.r.t. $W$ and $S$ is not. Substituting “general memory” by “chromatic
memory”, we obtain a definition of the chromatic memory complexity of $W$,
which is denoted by $\mathsf{ChrMem}(W)$.

For any $W$, we have $\mathsf{GenMem}(W)\leq\mathsf{ChrMem}(W)$. Our paper
revolves around a question from the Ph.D. thesis of Kopczyński [12].

######  Question 1.

Is this true that $\mathsf{GenMem}(W)=\mathsf{ChrMem}(W)$ for every winning
condition $W$?

To understand Kopczyński’s motivation, we first have to go back to 1969, when
Büchi and Landweber [4] established that $\mathsf{ChrMem}(W)$ is finite for
all $\omega$-regular $W$. An obvious corollary of this is that
$\mathsf{GenMem}(W)$ is also finite for all $\omega$-regular $W$. Since then,
there is an unfinished quest of _exactly characterizing_ $\mathsf{ChrMem}(W)$
and $\mathsf{GenMem}(W)$ for $\omega$-regular $W$. In particular, it is open
whether $\mathsf{ChrMem}(W)$ and $\mathsf{GenMem}(W)$ are computable given an
$\omega$-regular $W$ as an input (assuming $W$ is given, say, in a form of a
non-deterministic Büchi automaton recognizing $W$).

In his Ph.D. thesis, Kopczyński contributed to this question by giving an
algorithm computing $\mathsf{ChrMem}(W)$ for prefix-independent
$\omega$-regular $W$ (a winning condition is called prefix-independent if it
is invariant under adding and removing finite prefixes). Prior to that, he
published a weaker version of this result in [11]. He asked Question 1 to find
out, whether his algorithm also computes $\mathsf{GenMem}(W)$ for prefix-
independent $\omega$-regular $W$. His other motivation was that the same
chromatic memory structure can be used in different arenas. Indeed, transition
functions of chromatic memory structures can be defined over colors so that we
do not have to specify them individually for each arena.

Question 1 was recently answered by Casares in [6]. Namely, for every
$n\in\mathbb{N}$ he gave a _Muller_ condition $W$ over $n$ colors with
$\mathsf{GenMem}(W)=2$ and $\mathsf{ChrMem}(W)=n$.

######  Definition 1.

A winning condition $W\subseteq C^{\omega}$ is Muller if $C$ is finite and
$\alpha\in W\iff\beta\in W$ for any two $\alpha,\beta\in C^{\omega}$ that have
the same sets of colors occurring infinitely often in them.

Every Muller condition is prefix-independent and $\omega$-regular. Hence, we
now know that Kopczyński’s algorithm does not always compute
$\mathsf{GenMem}(W)$ for prefix-independent $\omega$-regular $W$. It is still
open whether some other algorithm does this job.

In a follow-up work, Casares, Colcombet and Lehtinen [7] achieve a larger gap
between $\mathsf{GenMem}(W)$ and $\mathsf{ChrMem}(W)$. Namely, they construct
a Muller $W$ over $n$ colors such that $\mathsf{GenMem}(W)$ is linear in $n$
and $\mathsf{ChrMem}(W)$ is exponential in $n$.

It is worth mentioning that Casares, Colcombet and Lehtinen derive these
examples from their new automata-theoretic characterizations of
$\mathsf{ChrMem}(W)$ and $\mathsf{GenMem}(W)$ for Muller $W$. First, Casares
[6] showed that $\mathsf{ChrMem}(W)$ equals the minimal size of a
deterministic Rabin automaton, recognizing $W$, for every Muller $W$. Second,
Casares, Colcombet and Lehtinen [7] showed that $\mathsf{GenMem}(W)$ equals
the minimal size of a good-for-games Rabin automaton, recognizing $W$, for
every Muller $W$. The latter result complements an earlier work by
Dziembowski, Jurdziński and Walukiewicz [10], who characterized
$\mathsf{GenMem}(W)$ for Muller $W$ in terms of their Zielonka’s trees [15].

These examples, however, do not answer a natural follow-up question – can the
gap between $\mathsf{GenMem}(W)$ and $\mathsf{ChrMem}(W)$ be infinite? To
answer it, we have to go beyond Muller and even $\omega$-regular conditions
(because $\mathsf{ChrMem}(W)$ is finite for them).

######  Question 2.

Is it true that for every finite set of colors $C$ and for every winning
condition $W\subseteq C^{\omega}$ we have
$\mathsf{GenMem}(W)<+\infty\implies\mathsf{ChrMem}(W)<+\infty$?

######  Remark 1.

If we do not insist on finiteness of $C$, a negative answer to Question 2
follows from the example of Casares. Namely, for every $n$ he defines a
winning condition $W_{n}\subseteq\\{1,2,\ldots n\\}^{\omega}$, consisting of
all $\alpha\in\\{1,2,\ldots n\\}^{\omega}$ such that there are exactly two
numbers from 1 to $n$ that occur infinitely often in $\alpha$. He then shows
that $\mathsf{GenMem}(W_{n})=2$ and $\mathsf{ChrMem}(W_{n})=n$ for every $n$.
We can now consider the union of these winning conditions $\cup_{n\geq
2}W_{n}$, which is a winning condition over $C=\mathbb{N}$. On one hand,
$\mathsf{GenMem}(\cup_{n\geq 2}W_{n})=2$ because every arena has only finitely
many natural numbers as colors, and hence $\cup_{n\geq 2}W_{n}$ coincides with
$W_{n}$ for some $n$ there. On the other hand, we have
$\mathsf{ChrMem}(\cup_{n\geq 2}W_{n})\geq\mathsf{ChrMem}(W_{n})=n$ for every
$n$, which means that $\mathsf{ChrMem}(\cup_{n\geq 2}W_{n})=+\infty$.

In this paper, we answer negatively to Question 2.

######  Theorem 1.

There exists a finite set of colors $C$ and a winning condition $W\subseteq
C^{\omega}$ such that $\mathsf{GenMem}(W)=2$ and $\mathsf{ChrMem}(W)=+\infty$.

Topologically, our $W$ belongs to the $\Sigma_{2}^{0}$-level of the Borel
hierarchy. Next, the size of $C$ in our example is 5, and there is a chance
that it can be reduced. In turn, $\mathsf{GenMem}(W)$ is optimal because
$\mathsf{GenMem}(W)=1$ implies $\mathsf{ChrMem}(W)=1$ (one state of general
memory is equally useless as one state of chromatic memory).

We call our $W$ the “Rope Ladder” condition. We define it in Section 3. The
upper bound on $\mathsf{GenMem}(W)$ and the lower bound on
$\mathsf{ChrMem}(W)$ are given in Section 4 and in Section 5, respectively.
Before that, we give Preliminaries in Section 2.

### Further open questions

Still, some intriguing variations of Question 2 remain open. For example, it
is interesting to obtain Theorem 1 for a closed condition, i.e. a condition in
the $\Pi^{0}_{1}$-level of the Borel hierarchy, or equivalently, a condition
given by a set of prohibited finite prefixes. In the game-theoretic
literature, such conditions are usually called safety conditions. Our $W$ is
an infinite union of safety conditions. In [9], Colcombet, Fijalkow and Horn
give a characterization $\mathsf{GenMem}(W)$ for safety $W$. Recently, Bouyer,
Fijalkow, Randour,and Vandenhove [5] obtained a characterization of
$\mathsf{ChrMem}(W)$ for safety $W$.

######  Problem 1.

Construct a finite set of colors $C$ and a safety winning condition
$W\subseteq C^{\omega}$ such that $\mathsf{GenMem}(W)<\infty$ and
$\mathsf{ChrMem}(W)=+\infty$.

It is equally interesting to obtain Theorem 1 for a prefix-independent $W$, as
our $W$ is not prefix-independent.

######  Problem 2.

Construct a finite set of colors $C$ and a prefix-independent winning
condition $W\subseteq C^{\omega}$ such that $\mathsf{GenMem}(W)<\infty$ and
$\mathsf{ChrMem}(W)=+\infty$.

There is also a variation of Question 2 related to a paper of Bouyer, Le Roux,
Oualhadj, Randour, and Vandenhove [3]. In this paper, they introduce and study
the class of arena-independent finite-memory determined winning conditions.
When the set of colors $C$ is finite, this class can be defined as the class
of $W$ such that both $\mathsf{ChrMem}(W)$ and
$\mathsf{ChrMem}(C^{\omega}\setminus W)$ are finite333In their original
definition, the “memory structure” (see Preliminaries) must be the same in all
arenas. When $C$ is finite, this definition is equivalent, because there are
just finitely many chromatic memory structures up to a certain size. If none
of them works for all arenas, one can construct a finite arena where none of
them works. (meaning that both Protagonist and Antagonist can play optimally
w.r.t. $W$ using some constant number of states of chromatic memory).

First, Bouyer et al. obtain an automata-theoretic characterization of arena-
independent finite-memory determinacy. Second, they deduce a one-to-two-player
lifting theorem from it. Namely, they show that as long as both
$\mathsf{ChrMem}(W)$ and $\mathsf{ChrMem}(\lnot W)$ are finite in arenas
without the Antagonist’s nodes, the same is true for all arenas.

A natural step forward would be to study conditions $W$ for which both
$\mathsf{GenMem}(W)$ and $\mathsf{GenMem}(\lnot W)$ are finite. Unfortunately,
it is even unknown whether this is a larger class of conditions. This raises
the following problem.

######  Problem 3.

Construct a finite set of colors $C$ and a winning condition $W\subseteq
C^{\omega}$ such that $\mathsf{GenMem}(W)$ and $\mathsf{GenMem}(\lnot W)$ are
finite, but $\mathsf{ChrMem}(W)$ is infinite.

In fact, it is not clear if our $W$ from Theorem 1 solves this problem. We do
not know whether $\mathsf{GenMem}(\lnot W)$ is finite for this $W$.

Question 2 is also open over infinite arenas. There is a relevant result due
to Bouyer, Randour and Vandenhove [2], who showed that the class of $W$ for
which $\mathsf{ChrMem}(W)$ and $\mathsf{ChrMem}(\lnot W)$ are both finite in
infinite arenas coincides with the class of $\omega$-regular $W$. Thus, it
would be sufficient to give a non-$\omega$-regular $W$ for which both
$\mathsf{GenMem}(W)$ and $\mathsf{GenMem}(\lnot W)$ are finite in infinite
arenas.

Finally, let us mention a line of work which studied the relationship between
chromatic and general memory in the non-uniform setting. Namely, fix a single
arena $\mathcal{A}$ and some winning condition $W$, and then consider two
quantities: first, the minimal $k_{gen}$ such that $\mathcal{A}$ has an
optimal strategy with $k_{gen}$ states of general memory, and second, the
minimal $k_{chr}$ such that $\mathcal{A}$ has an optimal strategy with
$k_{chr}$ states of chromatic memory. In [14], Le Roux showed that if
$k_{gen}$ is finite, then $k_{chr}$ is also finite. There is no contradiction
with Theorem 1 because $k_{chr}$ depends not only on $k_{gen}$, but also on
$\mathcal{A}$. A tight bound on $k_{chr}$ in terms of $k_{gen}$ and the number
of nodes of $\mathcal{A}$ was obtained in [13].

##  2 Preliminaries

Notation. For a set $A$, we let $A^{*}$ and $A^{\omega}$ stand for the set of
all finite and the set of all infinite sequences of elements of $A$,
respectively. For $x\in A^{*}$, we let $|x|$ denote the length of $x$. We also
set $|x|=+\infty$ for $x\in A^{\omega}$. We let $\circ$ denote the function
composition. The set of positive integral numbers is denoted by
$\mathbb{Z}^{+}$.

###  2.1 Arenas

######  Definition 2.

Let $C$ be a non-empty set. A tuple $\mathcal{A}=\langle V_{P},V_{A},E\rangle$
is called an arena over the set of colors $C$ if the following conditions
hold:

  * •

$V_{P},V_{A},E$ are finite sets such that $V_{P}\cap V_{A}=\varnothing$,
$V_{P}\cup V_{A}\neq\varnothing$ and $E\subseteq(V_{P}\cup V_{A})\times
C\times(V_{P}\cup V_{A})$;

  * •

for every $s\in V_{P}\cup V_{A}$ there exist $c\in C$ and $t\in V_{P}\cup
V_{A}$ such that $(s,c,t)\in E$.

Elements of the set $V=V_{P}\cup V_{A}$ will be called nodes of $\mathcal{A}$.
Elements of $V_{P}$ will be called nodes controlled by Protagonist (or simply
Protagonist’s nodes). Similarly, elements of $V_{A}$ will be called nodes
controlled by Antagonist (or simply Antagonist’s nodes). Elements of $E$ will
be called edges of $\mathcal{A}$. For an edge $e=(s,c,t)\in E$ we define
$\mathsf{source}(e)=s,\mathsf{col}(e)=c$ and $\mathsf{target}(e)=t$. We
imagine $e\in E$ as an arrow which is drawn from the node $\mathsf{source}(e)$
to the node $\mathsf{target}(e)$ and which is colored into $\mathsf{col}(e)$.
Note that the second condition in the definition of an arena means that every
node has at least one out-going edge.

We extend the domain of $\mathsf{col}$ to the set $E^{*}\cup E^{\omega}$ by

$\mathsf{col}(e_{1}e_{2}e_{3}\ldots)=\mathsf{col}(e_{1})\mathsf{col}(e_{2})\mathsf{col}(e_{3})\ldots,\qquad
e_{1},e_{2},e_{3},\ldots\in E.$

A non-empty sequence $p=e_{1}e_{2}e_{3}\ldots\in E^{*}\cup E^{\omega}$ is
called a path if for any $1\leq i<|p|$ we have
$\mathsf{target}(e_{i})=\mathsf{source}(e_{i+1})$. We set
$\mathsf{source}(p)=\mathsf{source}(e_{1})$ and, if $p$ is finite,
$\mathsf{target}(p)=\mathsf{target}(e_{|p|})$. For technical convenience,
every node $v\in V$ is assigned a $0$-length path $\lambda_{v}$, for which we
set $\mathsf{source}(\lambda_{v})=\mathsf{target}(\lambda_{v})=v$ and
$\mathsf{col}(\lambda_{v})=\mbox{empty string}$.

Paths are sequences of edges, so we will say that some paths are prefixes of
the others. However, we have to define this for $0$-length paths. Namely, we
say that $\lambda_{v}$ is a prefix of a path $p$ if and only if
$\mathsf{source}(p)=v$.

###  2.2 Strategies

Let $\mathcal{A}=\langle V_{P},V_{A},E\rangle$ be an arena over the set of
colors $C$. A Protagonist’s strategy in $\mathcal{A}$ is any function

$S\colon\\{p\mid p\mbox{ is a finite path in $\mathcal{A}$ with
}\mathsf{target}(p)\in V_{P}\\}\to E,$

such that for every $p$ from the domain of $S$ we have
$\mathsf{source}(S(p))=\mathsf{target}(p)$. In this paper, we do not mention
Antagonist’s strategies, but, of course, they can be defined similarly.

The set of finite paths in $\mathcal{A}$ is the set of positions of the game.
Possible starting positions are $0$-length paths $\lambda_{s},s\in V$. When
the starting position444We do not have to redefine $S$ for every starting
position. The same $S$ can be played from any of them. is $\lambda_{s}$, we
say that the game starts at $s$. Now, consider any finite path $p$.
Protagonist is the one to move after $p$ if and only if $t=\mathsf{target}(p)$
is a Protagonist’s node. In this situation, Protagonist must choose some edge
starting at $t$. A Protagonist’s strategy fixes this choice for every $p$ with
$\mathsf{target}(p)\in V_{P}$. We then append this edge to $p$ and get the
next position in the game. Antagonist acts the same for those $p$ such that
$\mathsf{target}(p)$ is an Antagonist’s node.

Let us define paths that are consistent with a Protagonist’s strategy $S$.
First, any 0-length path $\lambda_{v}$ is consistent with $S$. Now, a non-
empty path $p=e_{1}e_{2}e_{3}\ldots$ (which may be finite or infinite) is
consistent with $S$ if the following holds:

  * •

if $\mathsf{source}(p)\in V_{P}$, then
$e_{1}=S(\lambda_{\mathsf{source}(p)})$;

  * •

for every $1\leq i<|p|$, if $\mathsf{target}(e_{i})\in V_{P}$, then
$e_{i+1}=S(e_{1}e_{2}\ldots e_{i})$.

For brevity, paths that are consistent with $S$ will also be called _plays
with_ $S$. For a node $v$, we let $\mathsf{FinitePlays}(S,v)$ and
$\mathsf{InfinitePlays}(S,v)$ denote the set of finite plays with $S$ that
start at $v$ and the set of infinite plays with $S$ that start at $v$,
respectively. For $U\subseteq V$, we define
$\mathsf{FinitePlays}(S,U)=\bigcup_{v\in U}\mathsf{FinitePlays}(S,v)$ and
$\mathsf{InfinitePlays}(S,U)=\bigcup_{v\in U}\mathsf{InfinitePlays}(S,v)$.

###  2.3 Memory structures

Let $\mathcal{A}=\langle V_{P},V_{A},E\rangle$ be an arena over the set of
colors $C$. A memory structure in $\mathcal{A}$ is a tuple
$\mathcal{M}=\langle M,m_{init},\delta\rangle$, where $M$ is a finite set,
$m_{init}\in M$ and $\delta\colon M\times E\to M$. Elements of $M$ are called
states of $\mathcal{M}$, $m_{init}$ is called the initial state of
$\mathcal{M}$ and $\delta$ is called the transition function of $\mathcal{M}$.
Given $m\in M$, we inductively define the function $\delta(m,\cdot)$ over
arbitrary finite sequences of edges:

$\displaystyle\delta(m,\mbox{empty sequence})$ $\displaystyle=m,$
$\displaystyle\delta(m,se)$ $\displaystyle=\delta(\delta(m,s),e),\qquad s\in
E^{*},e\in E.$

In other words, $\delta(m,s)$ is the state of $\mathcal{M}$ it transits to
from the state $m$ if we fed $s$ to it.

A memory structure $\mathcal{M}=\langle M,m_{init},\delta\rangle$ is called
chromatic if $\delta(m,e_{1})=\delta(m,e_{2})$ for every $m\in M$ and for
every $e_{1},e_{2}\in E$ with $\mathsf{col}(e_{1})=\mathsf{col}(e_{2})$. In
this case, there exists $\sigma\colon M\times C\to M$ such that
$\delta(m,e)=\sigma(m,\mathsf{col}(e))$. In other words, we can view
$\mathcal{M}$ as a deterministic finite automaton over $C$, with $\sigma$
being its transition function.

A strategy $S$ is built on top of a memory structure $\mathcal{M}$ if we have
$S(p_{1})=S(p_{2})$ for any two paths $p_{1},p_{2}$ with
$\mathsf{target}(p_{1})=\mathsf{target}(p_{2})$ and
$\delta(m_{init},p_{1})=\delta(m_{init},p_{2})$. In this case, we sometimes
simply say that $S$ is an $\mathcal{M}$-strategy. To define an
$\mathcal{M}$-strategy $S$, it is sufficient to give its _next-move function_
$n_{S}\colon V_{P}\times M\to E$. For $v\in V_{P}$ and $m\in M$, the value of
$n_{S}(v,m)$ determines what $S$ does for paths that end at $v$ and bring
$\mathcal{M}$ to $m$ from $m_{init}$.

A strategy $S$ built on top of a memory structure $\mathcal{M}$ with $k$
states is called a strategy with $k$ states of general memory. If
$\mathcal{M}$ is chromatic, then $S$ is a strategy with $k$ states of
chromatic memory.

For brevity, if $S$ is an $\mathcal{M}$-strategy and $p$ is a finite path, we
say that $\delta(m_{init},p)$ is the state of $S$ after $p$.

###  2.4 Winning conditions and their memory complexity

A winning condition is any set $W\subseteq C^{\omega}$. We say that a
Protagonist’s strategy $S$ is winning from a node $u$ w.r.t. $W$ if the image
of $\mathsf{InfinitePlays}(S,u)$ under $\mathsf{col}$ is a subset of $W$. In
other words, any infinite play from $u$ against $S$ must give a sequence of
colors belonging to $W$. Now, a Protagonist’s strategy $S$ is called optimal
w.r.t. $W$ if there exists no node $u$ such that some Protagonist’s strategy
is winning from $u$ w.r.t. $W$ and $S$ is not.

We let $\mathsf{GenMem}(W)$ be the minimal $k\in\mathbb{Z}^{+}$ such that in
every arena $\mathcal{A}$ over $C$ there exists a Protagonist’s strategy with
$k$ states of general memory which is optimal w.r.t. $W$. If no such $k$
exists, we set $\mathsf{GenMem}(W)=+\infty$. Likewise, we let
$\mathsf{ChrMem}(W)$ be the minimal $k\in\mathbb{Z}^{+}$ such that in every
arena $\mathcal{A}$ over $C$ there exists a Protagonist’s strategy with $k$
states of general memory which is optimal w.r.t. $W$. Again, if no such $k$
exists, we set $\mathsf{ChrMem}(W)=+\infty$.

##  3 The “Rope Ladder” Condition

Consider the partially ordered set
$\Omega=(\mathbb{N}\times\\{0,1\\},\preceq)$, where $\preceq$ is defined by

$\forall(n,a),(m,b)\in\mathbb{N}\times\\{0,1\\}\qquad(n,a)\preceq(m,b)\iff(n,a)=(m,b)\mbox{
or }n<m.$

$(0,0)$$(0,1)$$(1,0)$$(1,1)$$(2,0)$$(2,1)$$\vdots$$\vdots$

Above is its Hasse diagram, with arrows representing $\preceq$ (they are
directed from bigger elements to smaller elements):

We will use an abbreviation $\mathbf{\overline{0}}=(0,0)$. Next, we let
$\mathbb{M}$ be the set of all functions $f\colon\Omega\to\Omega$ that are
monotone w.r.t. $\preceq$. Being monotone w.r.t. $\preceq$ means that
$x\preceq y\implies f(x)\preceq f(y)$ for all $x,y\in\Omega$.

######  Definition 3.

The Rope Ladder condition is a set $\mathsf{RL}\subseteq\mathbb{M}^{\omega}$,
consisting of all infinite sequences
$(f_{1},f_{2},f_{3},\ldots)\in\mathbb{M}^{\omega}$ for which there exists
$(N,b)\in\Omega$ such that $f_{n}\circ\ldots\circ f_{2}\circ
f_{1}(\mathbf{\overline{0}})\preceq(N,b)$ for all $n\geq 1$.

We will use the following informal terminology with regard to $\mathsf{RL}$.
Imagine that there is an ant which can move over the elements of $\Omega$.
Initially, it sits at $\mathbf{\overline{0}}$. Next, take any sequence
$(f_{1},f_{2},f_{3},\ldots)\in\mathbb{M}^{\omega}$. We start moving the ant by
applying functions from the sequence to the position of the ant. Namely, we
first move the ant from $\mathbf{\overline{0}}$ to
$f_{1}(\mathbf{\overline{0}})$, then from $f_{1}(\mathbf{\overline{0}})$ to
$f_{2}\circ f_{1}(\mathbf{\overline{0}})$, and so on. Now,
$(f_{1},f_{2},f_{3},\ldots)\in\mathsf{RL}$ if and only if there exists a
“layer” in $\Omega$ which is never exceeded by the ant.

######  Remark 2.

$\mathsf{RL}$ is defined over infinitely many colors, but for our lower bound
on its chromatic memory complexity we will consider its restriction to some
finite subset of $\mathbb{M}$.

To illustrate these definitions, we establish the following fact. It can also
be considered as a warm-up for our lower bound.

######  Fact 1.

$\mathsf{ChrMem}(\mathsf{RL})>1$.

###### Proof.

First, consider $u,v\colon\Omega\to\Omega$, depicted below:

$(0,0)$$(0,1)$$(1,0)$$(1,1)$$(2,0)$$(2,1)$$\vdots$$\vdots$$u$$(0,0)$$(0,1)$$(1,0)$$(1,1)$$(2,0)$$(2,1)$$\vdots$$\vdots$$v$

These functions are defined by arrows that direct each element of $\Omega$ to
the value of the function on this element. Formally, $u((n,a))=(n+1,a)$ and
$v((n,a))=(n+1,1-a)$ for every $(n,a)\in\Omega$. It holds that
$u,v\in\mathbb{M}$ because they both always increase the first coordinate by
1.

We also consider the following two functions
$f_{0},f_{1}\colon\Omega\to\Omega$:

$f_{b}((n,a))=\begin{cases}(n,a)&(n,a)=(0,0),(0,1)\mbox{ or }(1,b),\\\
(n+1,a)&\mbox{otherwise},\end{cases}\qquad b\in\\{0,1\\}$ (1)

For the reader’s convenience, we depict them as well.

$(0,0)$$(0,1)$$(1,0)$$(1,1)$$(2,0)$$(2,1)$$\vdots$$\vdots$$f_{0}$$(0,0)$$(0,1)$$(1,0)$$(1,1)$$(2,0)$$(2,1)$$\vdots$$\vdots$$f_{1}$

To see that $f_{0},f_{1}\in\mathbb{M}$, observe that both functions have 3
fixed points, and at remaining points, they act by increasing the first
coordinate by 1. There could be a problem with monotonicity if below some
fixed point there were a point which is not a fixed point. However, the sets
of fixed points of $f_{0}$ and $f_{1}$ are downwards-closed w.r.t. $\preceq$.

Consider the following arena.

$u$$v$$f_{0}$$f_{1}$

The circle is controlled by Antagonist and the square is controlled by
Protagonist. Assume that the game starts in the circle. We first show that
Protagonist has a winning strategy w.r.t. $\mathsf{RL}$. Then we show that
Protagonist does not have a positional strategy which is winning w.r.t.
$\mathsf{RL}$. This implies that $\mathsf{ChrMem}(\mathsf{RL})>1$.

Let us start with the first claim. After the first move of Antagonist, the ant
moves either to $u(\mathbf{\overline{0}})=(1,0)$ or to
$v(\mathbf{\overline{0}})=(1,1)$. In the first case, Protagonist wins by
forever using the $f_{0}$-edge (the ant will always stay at $(1,0)$). In the
second case, Protagonist wins by always using the $f_{1}$-edge (the ant will
always stay at $(1,1)$).

Now we show that every positional strategy of Protagonist is not winning
w.r.t. $\mathsf{RL}$. In fact, there are just 2 Protagonist’s positional
strategies – one which always uses the $f_{0}$-edge and the other which always
uses the $f_{1}$-edge. The first one loses if Antagonist goes by the $v$-edge.
Then the ant moves to $v(\mathbf{\overline{0}})=(1,1)$. If we start applying
$f_{0}$ to the ant’s position, the first coordinate of the ant will get
arbitrarily large. Similarly, the second Protagonist’s positional strategy
loses if Antagonist goes by the $u$-edge.∎∎

##  4 Upper Bound on the General Memory

In this section, we establish

######  Proposition 1.

$\mathsf{GenMem}(\mathsf{RL})=2$.

By Fact 1, we only have to show an upper bound
$\mathsf{GenMem}(\mathsf{RL})\leq 2$. For that, for every arena $\mathcal{A}$
over $\mathbb{M}$ and for every Protagonist’s strategy $S_{1}$ in
$\mathcal{A}$ we construct a Protagonist’s strategy $S_{2}$ with 2 states of
general memory for which the following holds: for every node $v$ of
$\mathcal{A}$, if $S_{1}$ is winning w.r.t. $\mathsf{RL}$ from $v$, then so is
$S_{2}$.

We will use the following notation. Take any finite path $p=e_{1}\ldots e_{m}$
in $\mathcal{A}$. Define
$\mathsf{ant}(p)=\mathsf{col}(e_{m})\circ\ldots\circ\mathsf{col}(e_{2})\circ\mathsf{col}(e_{1})(\mathbf{\overline{0}})$.
In other words, $\mathsf{ant}(p)$ is the position of the ant after the path
$p$. In case when $p$ is a $0$-length path, we set
$\mathsf{ant}(p)=\mathbf{\overline{0}}$. We also write $\mathsf{layer}(p)$ for
the first coordinate of $\mathsf{ant}(p)$.

Let $U$ be the set of nodes of $\mathcal{A}$ from which $S_{1}$ is winning
w.r.t. $\mathsf{RL}$. By definition of $\mathsf{RL}$, for every
$P\in\mathsf{InfinitePlays}(S_{1},U)$ there exists $N\in\mathbb{N}$ such that
$\mathsf{layer}(p)\leq N$ for every finite prefix $p$ of $P$. The first step
of our argument is to change the quantifiers here. That is, we obtain a
strategy $S_{1}^{\prime}$ for which there exists some $N\in\mathbb{N}$ such
that $\mathsf{layer}(p)\leq N$ for every
$p\in\mathsf{FinitePlays}(S_{1}^{\prime},U)$.

We use an argument, similar to one which was used in [8] to show finite-memory
determinacy of multi-dimensional energy games. We call a play
$p\in\mathsf{FinitePlays}(S_{1},U)$ _regular_ if there exist two prefixes
$q_{1}$ and $q_{2}$ of $p$ such that, first, $q_{1}$ is shorter than $q_{2}$,
second, $\mathsf{target}(q_{1})=\mathsf{target}(q_{2})$, and third,
$\mathsf{ant}(q_{1})=\mathsf{ant}(q_{2})$. In other words, $q_{1}$ and $q_{2}$
must lead to the same node in $\mathcal{A}$ and to the same position of the
ant in $\Omega$. We stress that $q_{2}$ might coincide with $p$, but $q_{1}$
must be a proper prefix of $p$. If $p\in\mathsf{FinitePlays}(S_{1},U)$ is not
regular, then we call it _irregular_.

First, we show that there are only finitely many irregular plays in the set
$\mathsf{FinitePlays}(S_{1},U)$. Note that any prefix of an irregular play is
irregular. Thus, irregular plays form a collection of trees with finite
branching (for each $u\in U$ there is a tree of irregular plays that start at
$u$). Assume for contradiction that there are infinitely many irregular plays.
Then, by Kőnig’s lemma, there exists an infinite branch in one of our trees.
It gives some $P\in\mathsf{InfinitePlays}(S_{1},U)$ whose finite prefixes are
all irregular. However, $P$ must be winning for Protagonist w.r.t.
$\mathsf{RL}$. In other words, there exists $N\in\mathbb{N}$ such that
$\mathsf{layer}(p)\leq N$ for every finite prefix $p$ of $P$. So, if $p$
ranges over finite prefixes of $P$, then $\mathsf{ant}(p)$ takes only finitely
many values. Hence, there exist a node $v$ of $\mathcal{A}$ and some
$(n,b)\in\Omega$ such that $v=\mathsf{target}(p)$ and $(n,b)=\mathsf{ant}(p)$
for infinitely many prefixes $p$ of $P$. Consider any two such prefixes. A
longer one is regular because the shorter one is its prefix and leads to the
same node in $\mathcal{A}$ and to the same position of the ant. This is a
contradiction.

We now define $S_{1}^{\prime}$. It will maintain the following invariant for
plays that start at $U$: if $p_{cur}$ is the current play, then there exists
an irregular $p\in\mathsf{FinitePlays}(S_{1},U)$ such that
$\mathsf{target}(p_{cur})=\mathsf{target}(p)$ and
$\mathsf{ant}(p_{cur})=\mathsf{ant}(p)$. Since there are only finitely many
irregular plays, this invariant implies that $\mathsf{ant}(p_{cur})$ takes
only finitely many values over
$p_{cur}\in\mathsf{FinitePlays}(S_{1}^{\prime},U)$, as required from
$S_{1}^{\prime}$.

To maintain the invariant, $S_{1}^{\prime}$ plays as follows. In the
beginning, $p_{cur}=\lambda_{w}$ for some $w\in U$. Hence, we can set
$p=\lambda_{w}$ also. Indeed, $\lambda_{w}\in\mathsf{FinitePlays}(S_{1},U)$
and it is irregular as it has no proper prefixes. Let us now show how to
maintain the invariant. Consider any play $p_{cur}$ with $S_{1}^{\prime}$ for
which there exists an irregular $p\in\mathsf{FinitePlays}(S_{1},U)$ such that
$\mathsf{target}(p_{cur})=\mathsf{target}(p)$ and
$\mathsf{ant}(p_{cur})=\mathsf{ant}(p)$. In this position, if its
Protagonist’s turn to move, $S_{1}^{\prime}$ makes the same move as $S_{1}$
from $p$. As a result, some edge $e$ is played. Observe that
$pe\in\mathsf{FinitePlays}(S_{1},U)$. In turn, our new current play with
$S_{1}^{\prime}$ is $p_{cur}e$. We have that
$\mathsf{target}(p_{cur}e)=\mathsf{target}(pe)=\mathsf{target}(e)$ and
$\mathsf{ant}(p_{cur}e)=\mathsf{col}(e)\big{(}\mathsf{ant}(p_{cur})\big{)}=\mathsf{col}(e)\big{(}\mathsf{ant}(p)\big{)}=\mathsf{ant}(pe)$.
So, if $pe$ is irregular, then the invariant is maintained. Now, assume that
$pe$ is regular. Then there are two prefixes $q_{1}$ and $q_{2}$ of $pe$ such
that, first, $q_{1}$ is shorter than $q_{2}$, second,
$\mathsf{target}(q_{1})=\mathsf{target}(q_{2})$, and third,
$\mathsf{ant}(q_{1})=\mathsf{ant}(q_{2})$. Since $p$ is irregular, $q_{2}$
cannot be a prefix of $p$. Hence, $q_{2}=pe$. By the same reason, $q_{1}$ is
irregular. Thus, invariant is maintained if we set the new value of $p$ be
$q_{1}$. Indeed,
$\mathsf{target}(p_{cur}e)=\mathsf{target}(pe)=\mathsf{target}(q_{2})=\mathsf{target}(q_{1})$
and
$\mathsf{ant}(p_{cur}e)=\mathsf{ant}(pe)=\mathsf{ant}(q_{2})=\mathsf{ant}(q_{1})$.

We now turn $S_{1}^{\prime}$ into a strategy $S_{2}$ with 2 states of general
memory which is winning w.r.t. $\mathsf{RL}$ from every node of $U$.

Preliminary definitions. Let $X$ be the set of nodes reachable from $U$ by
plays with $S_{1}^{\prime}$. Next, for $v\in X$, define
$\Omega_{v}\subseteq\Omega$ as the set of all $(n,b)\in\Omega$ such that
$(n,b)=\mathsf{ant}(p)$ for some $p\in\mathsf{FinitePlays}(S_{1}^{\prime},W)$
with $v=\mathsf{target}(p)$. In other words, $\Omega_{v}$ is the set of all
possible positions of the ant that can arise at $v$ if we play according to
$S_{1}^{\prime}$ from a node of $U$.

Now, take any $v\in X$. The set $\Omega_{v}$ is non-empty and, by our
requirements on $S_{1}^{\prime}$, finite. Hence, it has $1$ or $2$ maximal
elements w.r.t. $\preceq$. We will denote them by $M_{0}^{v}$ and $M_{1}^{v}$.
If $\Omega_{v}$ has just a single maximal element, then $M_{0}^{v}=M_{1}^{v}$.
If $\Omega_{v}$ has two different maxima, then let $M_{0}^{v}$ be the one
having $0$ as the second coordinate. Finally, for every $v\in X$ and for every
$b\in\\{0,1\\}$ fix some $p_{b}^{v}\in\mathsf{FinitePlays}(S_{1}^{\prime},U)$
such that $\mathsf{target}(p_{b}^{v})=v$ and
$\mathsf{ant}(p_{b}^{v})=M_{b}^{v}$.

Description of $S_{2}$. Two states of $S_{2}$ will be denoted by $0$ and $1$.
The initial state of $S_{2}$ is $0$. The next-move function of $S_{2}$ is
defined as follows. Assume that the state of $S_{2}$ is $I\in\\{0,1\\}$ and it
has to make a move from a node $v$. If $v\notin X$, it makes an arbitrary move
(this case does not matter for the argument below). Now, assume that $v\in X$.
Then $S_{2}$ make the same move as $S_{1}^{\prime}$ after $p_{I}^{v}$.

We now describe the memory structure of $S_{2}$. Assume that it receives an
edge $e$ when its state is $I\in\\{0,1\\}$. The new state $J\in\\{0,1\\}$ is
computed as follows. Denote $u=\mathsf{source}(e)$ and $v=\mathsf{target}(e)$.
If $u\notin X$ or $v\notin X$, then $J=0$ (again, this case is irrelevant for
the rest of the argument). Assume now that $u,v\in X$. If
$\mathsf{col}(e)\big{(}M_{I}^{u}\big{)}\in\Omega_{v}$, then we find some
$b\in\\{0,1\\}$ such that $\mathsf{col}(e)\big{(}M_{I}^{u}\big{)}\preceq
M_{b}^{v}$ and set $J=b$. Otherwise, we set $J=0$.

Showing that $S_{2}$ is winning from $W$. First, we observe that
$\mathsf{target}(p)\in X$ for every $p\in\mathsf{FinitePlays}(S_{2},U)$ (in
other words, $S_{2}$ cannot leave $X$ if we start somewhere in $U$). Indeed,
assume for contradiction that some play with $S_{2}$ leaves $X$ from some node
$v\in X$. Let $I$ be the state of $S_{2}$ at the moment just before leaving
$X$. If it is a Protagonist’s turn to move, then it moves as $S_{1}^{\prime}$
after $p_{I}^{v}$. Recall that
$p_{I}^{v}\in\mathsf{FinitePlays}(S_{1}^{\prime},U)$. Thus, we obtain a
continuation of $p_{I}^{v}$ which is consistent with $S_{1}^{\prime}$ and
leads outside $X$. This contradicts the definition of $X$. Now, if it is an
Antagonist’s turn to move from $v$, then any continuation of $p_{I}^{v}$ by
one edge is consistent with $S_{1}^{\prime}$, so we obtain the same
contradiction.

Next, we show that for any play $p\in\mathsf{FinitePlays}(S_{2},U)$ we have
$\mathsf{ant}(p)\preceq M_{I}^{\mathsf{target}(p)}$, where $I$ is the state of
$S_{2}$ after $p$. This statement implies that $S_{2}$ is winning w.r.t.
$\mathsf{RL}$ from every node of $U$. Note that $M_{I}^{\mathsf{target}(p)}$
is well-defined thanks to the previous paragraph.

We prove this statement by induction on the length of $p$. Let us start with
the induction base. Assume that $|p|=0$ (then $p=\lambda_{w}$ for some $w\in
U$). The state of $S_{2}$ after $p$ is the initial state, that is, $0$. Thus,
we have to show that $\mathsf{ant}(p)\preceq M_{0}^{\mathsf{target}(p)}$. Note
that $p$ has length $0$ and hence is consistent with any strategy. In
particular, $p\in\mathsf{FinitePlays}(S_{1}^{\prime},U)$. Hence,
$\mathsf{ant}(p)\in\Omega_{\mathsf{target}(p)}$. If
$\Omega_{\mathsf{target}(p)}$ has just a single maximum, then
$\mathsf{ant}(p)$ does not exceed this maximum, as required. Now, if
$M_{0}^{\mathsf{target}(p)}\neq M_{1}^{\mathsf{target}(p)}$, then the second
coordinate of $M_{0}^{\mathsf{target}(p)}$ is $0$, so we have
$\mathsf{ant}(p)\preceq M_{0}^{\mathsf{target}(p)}$ just because
$\mathsf{ant}(p)=\mathbf{\overline{0}}$.

Next, we establish the induction step. Consider any
$p\in\mathsf{FinitePlays}(S_{2},U)$ of positive length and assume that for all
paths from $\mathsf{FinitePlays}(S_{2},U)$ of smaller length the statement is
already proved. We prove our statement for $p$. Let $e$ be the last edge of
$p$. Correspondingly, let $q$ be the part of $p$ preceding $e$. Denote
$u=\mathsf{target}(q)=\mathsf{source}(e)$ and
$v=\mathsf{target}(p)=\mathsf{target}(e)$

Any prefix of $p$ is also in $\mathsf{FinitePlays}(S_{2},U)$, so
$q\in\mathsf{FinitePlays}(S_{2},U)$. Therefore, our statement holds for $q$.
Namely, if $I$ is the state of $S_{2}$ after $q$, then $\mathsf{ant}(q)\preceq
M_{I}^{u}$.

Let $J$ be the state of $S_{2}$ after $p$. Our goal is to show that
$\mathsf{ant}(p)\preceq M_{J}^{v}$. Note that
$\mathsf{ant}(p)=\mathsf{col}(e)\big{(}\mathsf{ant}(q)\big{)}$ by definition
of $\mathsf{ant}$. Since $\mathsf{col}(e)\in\mathbb{M}$ is monotone and
$\mathsf{ant}(q)\preceq M_{I}^{u}$, we have that
$\mathsf{ant}(p)=\mathsf{col}(e)\big{(}\mathsf{ant}(q)\big{)}\preceq\mathsf{col}(e)\big{(}M_{I}^{u}\big{)}$.
It remains to show that $\mathsf{col}(e)\big{(}M_{I}^{u}\big{)}\preceq
M_{J}^{v}$. Note that $J$ is the state into which $S_{2}$ transits from the
state $I$ after receiving $e$. By definition of the memory structure of
$S_{2}$, it is sufficient to show that
$\mathsf{col}(e)\big{(}M_{I}^{u}\big{)}\in\Omega_{v}$.

By definition of $p_{I}^{u}$, we have that
$M_{I}^{u}=\mathsf{ant}(p_{I}^{u})$. Hence,
$\mathsf{col}(e)\big{(}M_{I}^{u}\big{)}=\mathsf{ant}(p_{I}^{u}e)$. The path
$p_{I}^{u}e$ starts at some node of $U$ and ends in $\mathsf{target}(e)=v$.
Thus, to establish $\mathsf{ant}(p_{I}^{u}e)\in\Omega_{v}$, it remains to show
consistency of $p_{I}^{u}e$ with $S_{1}^{\prime}$. We have
$p_{I}^{u}\in\mathsf{FinitePlays}(S_{1}^{\prime},U)$ by definition of
$p_{I}^{u}$. In turn, if Protagonist is the one to move from
$u=\mathsf{target}(p_{I}^{u})$, then $e=S_{1}^{\prime}(p_{I}^{u})$. Indeed,
$e$ is the edge played by $S_{2}$ from $u$ when its state is $I$. Hence,
$e=S_{1}^{\prime}(p_{I}^{u})$, by the definition of the next-move function of
$S_{2}$.

##  5 Lower Bound on the Chromatic Memory

In this section, we establish the following proposition.

######  Proposition 2.

There exists a finite set $C\subseteq\mathbb{M}$ such that
$\mathsf{ChrMem}(\mathsf{RL}\cap C^{\omega})=+\infty$.

We start by describing $C$. First, we put there $f_{0},f_{1}$ that are defined
in (1). Next, put there a function $h\colon\Omega\to\Omega$, defined by

$h((n,a))=\begin{cases}(n-1,a)&n>1\\\ (0,0)&n=0,1.\end{cases}$

For the reader’s convenience, it is depicted below:

$(0,0)$$(0,1)$$(1,0)$$(1,1)$$(2,0)$$(2,1)$$\vdots$$\vdots$$h$

Let us establish that $h\in\mathbb{M}$. Take any $(n,a),(m,b)\in\Omega$ such
that $(n,a)\preceq(m,b)$. We show that $h((n,a))\preceq h((m,b))$. If
$(n,a)=(m,b)$, then $h((n,a))=h((m,b))$. Now, if $(n,a)\neq(m,b)$, then $n<m$.
The first coordinates of $h((n,a))$ and $h((m,b))$ are $\max\\{0,n-1\\}$ and
$\max\\{0,m-1\\}$, respectively. If $m>1$, then
$\max\\{0,m-1\\}=m-1>\max\\{0,n-1\\}$, which implies that $h((n,a))\preceq
h((m,b))$. Now, if $m\leq 1$, then $n\leq 1$ also, which means that
$h((n,a))=h((m,b))=(0,0)$.

We will also put into $C$ two more functions
$p^{0},p^{1}\colon\Omega\to\Omega$, but to define them, we need some auxiliary
work.

######  Definition 4.

A function $f\colon\Omega\to\Omega$ is called incremental if for every
$(n,b)\in\Omega$ there exists $c\in\\{0,1\\}$ such that $f((n,b))=(n+1,c)$.

Let us first observe that every incremental $f\colon\Omega\to\Omega$ belongs
to $\mathbb{M}$. Indeed, take any $(n,a),(m,b)\in\Omega$ such that
$(n,a)\preceq(m,b)$. We have to show that $f((n,a))\preceq f((m,b))$. for
every incremental $f$. If $(n,a)=(m,b)$, we have $f((n,a))=f((m,b))$ .
Otherwise, $n<m$. Then $f((n,a))=(n+1,c)$ and $f((m,b))=(m+1,d)$ for some
$c,d\in\\{0,1\\}$. Since $n+1<m+1$, we have $f((n,a))\preceq f((m,b))$.

We say that two binary words $x,y\in\\{0,1\\}^{*}$ are _$Q$
-indistinguishable_ if there exists no deterministic finite automaton over
$\\{0,1\\}$ with at most $Q$ states which comes to different states on $x$ and
on $y$.

######  Lemma 1.

There exist two infinite sequences of bits
$\\{I_{n}^{0}\\}_{n=0}^{\infty}\in\\{0,1\\}^{\omega}$ and
$\\{I_{n}^{1}\\}_{n=0}^{\infty}\in\\{0,1\\}^{\omega}$ such that for every
$Q\in\mathbb{N}$ there exist $t\in\mathbb{N}$ and two $Q$-indistinguishable
binary words $x=x_{0}\ldots x_{t-1}$ and $y=y_{0}\ldots y_{t-1}$ of length $t$
such that:

$I_{0}^{x_{0}}\oplus\ldots\oplus I_{t-1}^{x_{t-1}}\neq
I_{0}^{y_{0}}\oplus\ldots\oplus I_{t-1}^{y_{t-1}}$

($\oplus$ denotes XOR).

###### Proof.

Let $A_{Q}$ be the number of deterministic finite automata over $\\{0,1\\}$
with at most $Q$ states. For $Q\in\mathbb{N}$, let $l_{Q}$ be any number such
that $2^{l_{Q}}>Q^{A_{Q}}$.

We split natural numbers in consecutive blocks $B_{1},B_{2},B_{3},\ldots$,
where

$B_{Q}=\\{l_{1}+\ldots+l_{Q-1},\ldots,l_{1}+\ldots+l_{Q-1}+l_{Q}-1\\}$

(so that $|B_{Q}|=l_{Q}$). We first define $I^{0}_{n},I^{1}_{n}$ for $n\in
B_{1}$, then for $n\in B_{2}$, and so on. The requirement of the lemma for $Q$
will be guaranteed after we define our sequences in the first $Q$ blocks.

More specifically, assume that our sequences are already defined in the first
$Q-1$ blocks. We have to define them in $B_{Q}$ in some way that satisfies the
requirement of the lemma for $Q$. Since $2^{l_{Q}}>Q^{A_{Q}}$, there exist two
different $Q$-indistinguishable binary words $a,b\in\\{0,1\\}^{l_{Q}}$.
Indeed, to every binary word $w$ we can assign a tuple, where for all
deterministic finite automaton $\mathcal{A}$ with at most $Q$ states we have a
coordinate, indicating the state of $\mathcal{A}$ after reading $w$. The
number of such tuples is bounded by $Q^{A_{Q}}$. Hence, in $\\{0,1\\}^{l_{Q}}$
there are two different binary words $a,b$ with the same tuple assigned to
them. This means that $a$ and $b$ are $Q$-indistinguishable.

Let $t=l_{1}+\ldots+l_{Q}$ and

$x=\underbrace{00\ldots 0}_{l_{1}+\ldots+l_{Q-1}}a\in\\{0,1\\}^{t},\qquad
y=\underbrace{00\ldots 0}_{l_{1}+\ldots+l_{Q-1}}b\in\\{0,1\\}^{t}.$

Note that $x$ and $y$ are obtained from $a$ and $b$ by attaching the same
prefix. Hence, $x$ and $y$ are also $Q$-indistinguishable. We claim that we
can define $I^{0}_{n},I^{1}_{n}$ for $n\in B_{Q}$ in such a way that:

$I_{0}^{x_{0}}\oplus\ldots\oplus I_{t-1}^{x_{t-1}}\neq
I_{0}^{y_{0}}\oplus\ldots\oplus I_{t-1}^{y_{t-1}}.$ (2)

Since $a$ and $b$ are different, we have that $x$ and $y$ are also different.
But both $x$ and $y$ start with $l_{1}+\ldots+l_{Q-1}$ zeros. Hence, all the
indices where they differ belong to $B_{Q}$. Take any $m\in B_{Q}$ such that
$x_{m}\neq y_{m}$. Define $I^{0}_{n}=I^{1}_{n}=0$ for all $n\in
B_{Q}\setminus\\{m\\}$. It remains to define $I^{0}_{m}$ and $I^{1}_{m}$ in
such a way that (2) holds. Note that all the summands except $I^{x_{m}}_{m}$
and $I^{y_{m}}_{m}$ are already defined. Since $x_{m}\neq y_{m}$, one of these
summands is $I^{0}_{m}$ and the other is $I^{1}_{m}$. One of them is in the
left-hand side, and the other one is in the right-hand side. Hence, we can
define them in such a way that the inequality is true.∎∎

We now take sequences $\\{I_{n}^{0}\\}_{n=0}^{\infty}\in\\{0,1\\}^{\omega}$
and $\\{I_{n}^{1}\\}_{n=0}^{\infty}\in\\{0,1\\}^{\omega}$, satisfying Lemma 1,
and define $p^{0},p^{1}\colon\Omega\to\Omega$ as follows:

$p^{0}((n,b))=\Big{(}n+1,b\oplus I_{n}^{0}\Big{)},\qquad
p^{1}((n,b))=\Big{(}n+1,b\oplus I_{n}^{1}\Big{)}.$

Note that $p^{0},p^{1}$ are incremental. Hence, $p^{0},p^{1}\in\mathbb{M}$. We
set $C=\\{f_{0},f_{1},h,p^{0},q^{1}\\}$ and show that
$\mathsf{ChrMem}(\mathsf{RL}\cap C^{\omega})=+\infty$. For that, for every
$Q\in\mathbb{N}$, we show that $\mathsf{ChrMem}(\mathsf{RL}\cap
C^{\omega})>Q$. Fix any $Q\in\mathbb{N}$ and let $t\in\mathbb{N}$ and
$x=x_{0}\ldots x_{t-1}\in\\{0,1\\}^{t},y=y_{0}\ldots y_{t-1}\in\\{0,1\\}^{t}$
be such that $x$ and $y$ are $Q$-indistinguishable and

$I_{0}^{x_{0}}\oplus\ldots\oplus I_{t-1}^{x_{t-1}}\neq
I_{0}^{y_{0}}\oplus\ldots\oplus I_{t-1}^{y_{t-1}}$ (3)

(existence of such $t$, $x$ and $y$ is guaranteed by Lemma 1). Consider the
following arena:

$u$$\ldots$$\ldots$$v$$\ldots$$w$$p^{x_{0}}$$p^{y_{0}}$$p^{x_{1}}$$p^{y_{0}}$$p^{x_{t-1}}$$p^{y_{t-1}}$$h$$h$$f_{0}$$f_{1}$$t-1$
edges

All circles are controlled by Antagonist and the square is controlled by
Protagonist. The game starts at the node $u$. We claim that Protagonist has a
winning strategy w.r.t. $\mathsf{RL}$. Indeed, in the beginning, Antagonist
has two choices – to go through $p^{x_{0}},p^{x_{1}},\ldots,p^{x_{t-1}}$ or to
go through $p^{y_{0}},p^{y_{1}},\ldots,p^{y_{t-1}}$. In any case, upon
reaching $v$, the first coordinate of the ant will be $t$ (both $p^{0}$ and
$p^{1}$ always increase the first coordinate of the ant by 1). Then we go
through $t-1$ edges colored by $h$. As a result, the position of the ant at
$w$ will be either $(1,0)$ or $(1,1)$. If it is $(1,0)$, then Protagonist wins
by always using $f_{0}$. If it is $(1,1)$, then Protagonist wins by always
using $f_{1}$.

It remains to show that Protagonist has no winning strategy with at most $Q$
states of chromatic memory. Indeed, consider any Protagonist’s strategy $S$
with at most $Q$ states of chromatic memory. Our goal is to show that $S$ is
not winning. It is built on top of some chromatic memory structure with at
most $Q$ states. This memory structure, by definition, only reads colors of
edges. Hence, when we go from $u$ to $v$, we either feed
$p^{x_{0}}p^{x_{1}}\ldots p^{x_{t-1}}\in\\{p^{0},p^{1}\\}^{t}$ or
$p^{y_{0}}p^{y_{1}}\ldots p^{y_{t-1}}\in\\{p^{0},p^{1}\\}^{t}$ to it. We claim
that $S$ comes into the same state on these two sequences. Indeed, up to
renaming letters of the alphabet, we may assume that we feed $x=x^{0}\ldots
x^{t-1}$ and $y=y^{0}\ldots y^{t-1}$ to the memory structure of $S$. By
definition, $x$ and $y$ are $Q$-indistinguishable. Since the memory structure
of $S$ has at most $Q$ states, it must come into the same state on $x$ and
$y$. We conclude the state of $S$ at $v$, and hence at $w$, will be the same
in both possible plays. Thus, $S$ acts identically at $w$ in these two plays.

At the same time, there are two different possible positions of the ant at
$w$. More specifically, if the Antagonist goes through
$p^{x_{0}}p^{x_{1}}\ldots p^{x_{t-1}}$, the position of the ant will be

$\displaystyle\underbrace{h\circ\ldots\circ h}_{t-1}\circ
p^{x_{t-1}}\circ\ldots\circ p^{x_{1}}\circ p^{x_{0}}(\mathbf{\overline{0}})$
$\displaystyle=\underbrace{h\circ\ldots\circ h}_{t-1}\circ
p^{x_{t-1}}\circ\ldots\circ p^{x_{1}}((1,I^{x_{0}}_{0}))$
$\displaystyle=\underbrace{h\circ\ldots\circ
h}_{t-1}((t,I_{0}^{x_{0}}\oplus\ldots\oplus I_{t-1}^{x_{t-1}})$
$\displaystyle=(1,I_{0}^{x_{0}}\oplus\ldots\oplus I_{t-1}^{x_{t-1}}).$

Likewise, if the Antagonist goes through $p^{y_{0}}p^{y_{1}}\ldots
p^{y_{t-1}}$, the position of the ant will be

$\underbrace{h\circ\ldots\circ h}_{t-1}\circ p^{x_{t-1}}\circ\ldots\circ
p^{x_{1}}\circ
p^{x_{0}}(\mathbf{\overline{0}})=(1,I_{0}^{y_{0}}\oplus\ldots\oplus
I_{t-1}^{y_{t-1}}).$

Since $I_{0}^{x_{0}}\oplus\ldots\oplus I_{t-1}^{x_{t-1}}\neq
I_{0}^{y_{0}}\oplus\ldots\oplus I_{t-1}^{y_{t-1}}$ by (3), we conclude that
both $(1,0)$ and $(1,1)$ are possible positions of the ant at $w$. But once
again, $S$ acts in the same way at $w$ in both cases. Assume first that $S$
plays the $f_{0}$-edge when it first reaches $w$. Then $S$ loses if the ant
reached $w$ being in $(1,1)$. Indeed, after $S$ plays its first move at $w$,
the position of the ant becomes $f_{0}((1,1))=(2,1)$. If the first coordinate
of the ant is 2 or more, both $f_{0}$ and $f_{1}$ increase it by 1. Hence, no
matter what Protagonist does afterwards, the ant will get infinitely high in
$\Omega$. Likewise, if the first move of $S$ at $w$ is the $f_{1}$-edge, then
it loses if the ant reaches $w$ being in $(1,0)$.

## References

  * [1] Bloem, R., Chatterjee, K., and Jobstmann, B. Graph games and reactive synthesis.  In Handbook of Model Checking. Springer, 2018, pp. 921–962.
  * [2] Bouyer, P., Randour, M., and Vandenhove, P. Characterizing Omega-Regularity Through Finite-Memory Determinacy of Games on Infinite Graphs.  TheoretiCS, 2 (2023), 1–48.
  * [3] Bouyer, P., Le Roux, S., Oualhadj, Y., Randour, M., and Vandenhove, P. Games Where You Can Play Optimally with Arena-Independent Finite Memory.  Logical Methods in Computer Science, 18 (2022), 11:1-11:44.
  * [4] Büchi, J. R., and Landweber, L. H. Solving sequential conditions by finite-state strategies.  Transactions of the American Mathematical Society 138 (1969), 295–311.
  * [5] Bouyer, P., Fijalkow, N., Randour, M., and Vandenhove, P. How to Play Optimally for Regular Objectives?  In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), vol. 261 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 118:1–118:18.
  * [6] Casares, A. On the Minimisation of Transition-Based Rabin Automata and the Chromatic Memory Requirements of Muller Conditions.  In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022) (Dagstuhl, Germany, 2022), F. Manea and A. Simpson, Eds., vol. 216 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 12:1–12:17.
  * [7] Casares, A., Colcombet, T., and Lehtinen, K. On the size of good-for-games Rabin automata and its link with the memory in Muller games.  In 349th International Colloquium on Automata, Languages, and Programming (ICALP 2022), vol. 229 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 117:1–117:20.
  * [8] Chatterjee, K., Doyen, L., Henzinger, T. A., and Raskin, J.-F. Generalized mean-payoff and energy games.  In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) (2010), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
  * [9] Colcombet, T., Fijalkow, N., and Horn, F. Playing safe.  In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) (2014), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
  * [10] Dziembowski, S., Jurdzinski, M., and Walukiewicz, I. How much memory is needed to win infinite games?  In Proceedings of Twelfth Annual IEEE Symposium on Logic in Computer Science (1997), IEEE, pp. 99–110.
  * [11] Kopczyński, E. Omega-regular half-positional winning conditions.  In International Workshop on Computer Science Logic (2007), Springer, pp. 41–53.
  * [12] Kopczyński, E. Half-positional determinacy of infinite games.  PhD thesis, Warsaw University, 2008.
  * [13] Kozachinskiy, A. State complexity of chromatic memory in infinite-duration games.  arXiv preprint arXiv:2201.09297 (2022).
  * [14] Le Roux, S. Time-aware uniformization of winning strategies.  In Conference on Computability in Europe (2020), Springer, pp. 193–204.
  * [15] Zielonka, W. Infinite games on finitely coloured graphs with applications to automata on infinite trees.  Theoretical Computer Science 200, 1-2 (1998), 135–183.