# Radon Mitigation Applications at the Laboratorio Subterráneo de Canfranc
(LSC)
Published in MDPI, Special Issue “Studying the Universe from Spain”
https://doi.org/10.3390/universe8020112

J. Pérez-Pérez1,4 aaaCorresponding author. Current address: Affiliation 4.
Correspondence<EMAIL_ADDRESS>or<EMAIL_ADDRESS>, J.C.
Amare2, I.C. Bandac 1, A. Bayo1, S. Borjabad-Sánchez 1,
J.M. Calvo-Mozota 1,6,7, L. Cid-Barrio 1, R. Hernández-Antolín 1, B.
Hernández-Molinero 1,
P. Novella3, K. Pelczar4, C. Peña-Garay 1, B. Romeo1,5, A. Ortiz de Solórzano
2, M. Sorel3,
J. Torrent5, A. Usón3, A. Wojna-Pelczar4 and G. Zuzel4

###### Abstract

The Laboratorio Subterráneo de Canfranc (LSC) is the Spanish national hub for
low radioactivity techniques and the associated scientific and technological
applications. The concentration of the airborne radon is a major component of
the radioactive budget in the neighborhood of the detectors. The LSC hosts a
Radon Abatement System, which delivers a radon suppressed air with $1.1\pm
0.2$ mBq/m3 of 222Rn. The radon content in the air is continuously monitored
with an Electrostatic Radon Monitor. Measurements with the double beta decay
demonstrators NEXT-NEW and CROSS and the gamma HPGe detectors show the
important reduction of the radioactive background due to the purified air in
the vicinity of the detectors. We also discuss the use of this facility in the
LSC current program which includes NEXT-100, low background biology
experiments and radiopure copper electroformation equipment placed in the
radon-free clean room.

1 Laboratorio Subterráneo de Canfranc (LSC), Canfranc-Estación 22880, Spain
2 Centro de Astropartículas y Física de Altas Energías (CAPA), Universidad de
Zaragoza, E-50009 Zaragoza, Spain
3 Instituto de Física Corpuscular (IFIC), CSIC & Universtitat de València,
Calle Catedrático José Beltrán, 2, Paterna, E-46980
4 M. Smoluchowski Institute of Physics, Jagiellonian University, ul.
Łojasiewicza 11, 30-348 Kraków, Poland
5 Donostia International Physics Center, (DIPC), Paseo Manuel Lardizabal, 4,
Donostia-San Sebastián, E-20018, Spain
6 Universidad Internacional de La Rioja, Avenida de la Paz, 137, 26006
Logroño, La Rioja, Spain
7 Universidad Pública de Navarra, Campus de Arrosadia, 31006 Pamplona, Spain

##  I INTRODUCTION

Underground laboratories are the best places to explore science and develop
technology in ultra-low radioactive background [1]. These laboratories have a
rock shielding that blocks most of the cosmic rays, reducing the external
background of the experiments several orders of magnitude. On the other hand,
the surrounding rocks can have large concentrations of 232Th, 238U, and 235U.
These isotopes start the natural decay series that involve several
radioisotopes and the emission of alpha, beta and gamma particles (see Figure
1) [2].

Figure 1: _Radioactive chains. Left: 232Th decay chain; Right: 238U decay
chain. In the grey boxes the most important gamma peaks energies and decay
probabilities of the corresponding isotopes are presented._

One of the elements of these decay chains is radon, a noble gas that can be
emanated from the materials and increases laboratory air radioactivity due to
its unstable isotopes. (e.g., 222Rn from 238U, 219Rn from 235U and 220Rn from
232Th). The most important radioactive background source among these radon
isotopes is 222Rn from 238U chain, with the half-life of $3.82$ days. This
half-life is long enough to allow this radioactive isotope to escape from the
material’s surface, which increases significantly the overall radioactive
background.

In Figure 1 we used four different colours to identify isotopes: green for
isotopes that decay fast (hours, seconds or shorter), yellow for intermediate
decay time (days or months), red for long half-life isotopes (years) and white
for the stable isotopes (the end of the different chains). When the secular
equilibrium is broken, every isotope in red initiates a sub-chain in
equilibrium. Light colored radioisotopes and arrows show low probability decay
paths. Black downwards arrows represent alpha decays, while blue up-diagonal
ones, beta decays. Half-lifes of the isotope and decay probabilities of the
branch are indicated next to the arrows. Finally, grey floating boxes contain
the most relevant gamma energies emitted in the decays.

##  II LABORATORIO SUBTERRÁNEO DE CANFRANC

Laboratorio Subterráneo de Canfranc (LSC) [3] is located in the Spanish side
of the Pyrenees Mountains, under the Tobazo peak. It is situated between the
international Somport road tunnel (that connects Spain and France) and the old
train tunnel (not in use). The laboratory has a rock shielding of 800 m
(Figure 2), equivalent to approximately 2400 meter water equivalent (mwe),
that suppresses the cosmic muon flux by almost 5 orders of magnitude.

Figure 2: _Laboratorio Subterráneo de Canfranc (LSC) - Longitudinal geological
profile._

The total area of the underground laboratory is about 1600 m2, corresponding
to a volume of about 10000 m3. The laboratory is divided in four main areas:
Hall A, Hall B, Hall C, Hall D and Hall E. Inside the laboratory several
services are provided like a Clean Room (Class ISO 7 / Class 10000 and a Class
ISO 6 / Class 1000 in part of the room), an Ultralow Background Service (ULBS)
using Gamma Spectrometry with High Purity Germanium Detectors (HPGe) situated
in Hall C, a mechanical workshop, the Radon Abatement System (RAS) and a
liquid nitrogen production and distribution facility.

The fresh air inside the laboratory comes from the Rioseta air entrance,
located on surface at 1400 meters altitude. This air has to cross a 230 m
vertical tunnel followed by a 700 m horizontal concrete tunnel excavated in
the rock before being collected in a 100 m pipe that connects the tunnel and
the laboratory. The air arrives to the Air Conditioning Room (Sala de
Climatización, SC) of the laboratory and finally it is distributed in all the
rooms of the laboratory with steel pipes, with a flow of 25000 m3/h. This
quantity plus the return air vent is enough to exchange all the air of the
laboratory several times per hour.

The radon concentration in air is monitored with AlphaGuard detectors
(AlphaGuard Saphimo P30 in Hall A, B and C; AlphaGuard Saphimo P2000 in Hall
E). These detectors have a sensitivity of 1 CPM at 20 Bq/m3, a lower limit of
$\sim 2$ Bq/m3, and a calibration error of $\pm 3\%$. The average annual
activity in the underground lab common area is ($69.0\pm 0.3$) Bq/m3 with
daily, seasonal and annual fluctuations (see Figure 3 for Rn measurements
performed in Hall A). The values obtained in different experimental halls
inside LSC performed at the same time are compatibles [4]. The radon emanation
depends on several external factors including rain or snow melting because
water increases radon diffusion from the material surfaces and its later
emanation [2], [5], [6], [7], [8].

Figure 3: _Radon measurements inside Hall A. Light blue points show the daily
measurements and the blue line shows the weekly mean value._

A dedicated campaign of measurements was performed in the underground lab to
identify the spatial distribution of the radon sources [9]. An AlphaGuard P30
detector was placed in several locations between the air entrance at Rioseta
and the pipe that collects this air and guide it towards the Air Conditioning
Room situated inside the underground laboratory. We observed an increase in
the radon activity from about 20 Bq/m3 at the entrance on surface (Rioseta) to
approximately $\sim 70$ Bq/m3 at the entrance of the air inside the
laboratory. This increase is caused by the radon emanated by the concrete of
the two tunnels from the Rioseta entrance to the laboratory.

##  III RADON ABATEMENT SYSTEM

Figure 4: _Scheme of the distribution of the elements of the RAS at LSC._

The Radon Abatement System at LSC is a system that can provide very low radon-
concentration air, of about $\sim 1$ mBq/m3, with a flow from 180 to 220 m3/h.
For many applications, such level of radioactivity makes this air radon-free
(Rn-free) in practice. The daily consumption of both N2 and LN2 (Liquid
nitrogen) is larger than what LSC can produce. The RAS is used to create large
Rn-free spaces that are safe for people to work. The Rn-free air is cheaper
and also reduces the dependence from external LN2 suppliers.

The RAS machine was built by the company Apparatuses Technologies Construction
(ATEKO a.s.) from Czech Republic. For this reason, the radon-free air is also
named ATEKO-air [10].

Other underground laboratories have similar facilities to reduce the radon
activity [11], [12]. For example, there are several installations made by
ATEKO - Table I [13].

The RAS takes the ambient air and compresses it to 10 bar. Then, the air is
dried, filtered and sent to the cooling unit, where the air is cooled to a
temperature of -60 ºC. In the next step, the air is moved to two adsorption
columns with 1 m3 volume each, where active carbon captures the radon atoms.
Finally, the air temperature is adjusted to be heated back to room temperature
and filtered again. For a schematic view of the RAS system, see Figure 4.

At the LSC, there are two different types of piping for the ATEKO-air: a
pressurized Rn-free air line (7 bar) with several outlets at the Underground
Laboratory, and an atmospheric pressure line used by the NEXT experiment, with
over-pressures from 0 Pa to 5000 Pa (50 mbar). The RAS has been delivering
continuously Rn-free air during the last 4 years, with a downtime of 0.2% due
to maintenance.

Table I: _ATEKO s.a. installations in Underground Laboratories._ Underground Lab. | Country | Average Rn (Bq/m3) | Year | Air Flow [m3/h]
---|---|---|---|---
Modane | France | 15 | 2004 | 150
Gran Sasso | Italy | 80 | 2011 | 150
Gran Sasso | Italy | 80 | 2012 | 220
Yangyang | Korea | 40 | 2015 | 120
LSC | Spain | 70 | 2015 | 220
SURF | USA | 310 | 2017 | 300
Jin Ping | China | 40 | 2019 | 300

##  IV ELECTROSTATIC RADON MONITOR

Figure 5: _Left: Picture of the ERM. Right: Simulation of the electric field
lines inside the ERM detector._

The Electrostatic Radon Monitor (ERM) [10] is a low background electrostatic
detector that can measure in real time activities $<1$ mBq/m3 of 222Rn in the
air using a Silicon $\alpha$-particle Detector from Canberra model PIPS
1200-35-100AM as alpha detector. To evaluate the performance of the ATEKO-air,
this air is continuously flowing through the ERM with a slight overpressure of
0.3 barg. Its scheme and a real picture of the top flange is shown in Figure
5. On the right side of the figure, the simulation of the electric field in
the detector vessel is shown. The field is created by applying a high voltage
(several kV) to the vessel while the alpha detector (black disc in the neck)
installed on a top flange is connected to the ground potential. With the
simulation, we estimate that $\sim 90\%$ of the field lines cross the detector
surface.

The detection efficiency has two contributions: charge collection efficiency
and alpha detector efficiency. The charge collection is the process where the
218Po ions, produced after a 222Rn decay, are drifted to the alpha detector
and collected. The average charge collection efficiency estimated by a
detailed simulation of the vessel geometry with a volumetric efficiency of
$\sim 90\%$. Some dead volumes (e.g. above the alpha particle detector)
contribute to the remaining $10\%$ of the volume (see [10] for more details).
The intrinsic detection efficiency of the alpha detector is close to $\sim
50\%$ as the decays occur right at the detector’s surface (0 distance). It is
actually less than that due to the edge effects (like the detector rim etc.).
To measure the detection efficiency, a calibration with a 222Rn source was
performed. The detection efficiency of the ERM is $(30\pm 4)\%$ for the 218Po
and 214Po $\alpha$-peaks at the operational voltage of 8 kV (see Figure 6,
left). The detection efficiency is similar in all the peaks of both Polonium
isotopes (we tend to refer to peaks - lines - in the energy spectrum having in
mind the detection efficiency for particular Po decays). The quoted value
refers to 214Po, which is less sensitive to gas contamination.

To estimate the background of the detector, we closed the flow of ATEKO-air
during 1 month to reach the saturation regime - when the measured Rn
concentration is actually the activity of emanated Rn (see Figure 6, right).
This happens when the detector is sealed (no gas is flushed), and the emanated
Rn activity has enough time to build up (saturate) to equilibrium between
emanation and decay. The activity of the radon emanated from the detector in
saturation is $(3.0\pm 0.5)$ mBq, which results in a small contribution (about
10 $\%$ of the saturation value) during normal operation. The estimated
detection limit of the detector is 0.7 mBq/m3.

Figure 6: _Left: Overall measured detection efficiency of the ERM for the
218Po and 214Po peaks as function of the operational voltage, HHV (High High
Voltage). Right: The activity of radon emanated from the ERM detector (in
saturation)._

A gas panel was designed to permit the operation of the ERM detector in
various configurations (Figure 7 shows the scheme of the detector and the gas
panel). There are three different gas inlets: one for N2, one for the ATEKO-
air directly from the RAS and the other one for different uses. Currently, the
detector is configured to input the ATEKO-air that comes back from NEXT after
flushing inside the lead castle, around the detector. A built-in 226Ra
calibration source (that emits 222Rn) is connected to the gas panel. A gas
pump is used to force circulation of the air through the detector.

Figure 7: _Schematic of the ERM detector and gas panel._

To see if there is a dependency of the residual Rn in the ATEKO air on the Rn
concentration outside the detector (input air), a study was made (In Figure 8)
by comparing the daily activity measured with the AlphaGuards (normal air) and
the daily activity measured with the ERM (ATEKO-air). The AlphaGuard detector
performs a measurement every 10 minutes, daily mean values were considered. In
the case of ERM, some measurements are several days long; in this case we
considered the corresponding mean value. The colored areas around the lines
include the 1-sigma error. No clear correlation was observed between the Rn
content in the ATEKO line and in the laboratory air. For this reason, it is
mandatory to have dedicated detectors - ERM and AlphaGuard, to monitor the
activity of the ATEKO-air and the external background, respectively.

Figure 8: _Comparison of radon activities vs time. We show the radon activity
in Hall-A measured with an AlphaGuard (in red) in units shown in the left side
y-axis and with the ERM (in blue) in units shown in the right side y-axis._

The ATEKO-air is very stable in time, demonstrated by calculating the mean
value of the activities for the first half of 2020 and 2021. The mean activity
was $1.1\pm 0.2$ mBq/m3, in 2020 and also in 2021. It shows that the
performance of the active carbon is good for long time usage. For this
measurements the outlet flow from the ATEKO system was 185 m3/h. We also
evaluated how much Rn activity varies with the air flow selected in the ATEKO
machine. From June 8th to June 15th 2020, the flow of the ATEKO-air was
increased to maximum capacity, that is 220 m3/h, with a mean activity of
$1.0\pm 0.2$ mBq/m3 statistically compatible with the usual mean activity.
This measurement was long enough to demonstrate no significant differences in
activity between flows. The energy consumption required to generate a unit of
flux (about 1 Nm3/h) of ATEKO-air depends on the outlet flux level produced by
the system (see Figure 9). Therefore, activity is not an important factor to
select the flow of Rn-free air.

Figure 9: _Energy consumption required to generate a unit of flux (about 1
Nm3/h) of ATEKO-air depends on the outlet flux level produced by the system_

##  V ATEKO-AIR TO NEXT

The first experiment benefiting from the ATEKO-air in the underground lab was
NEXT (Neutrino Experiment with a Xenon TPC) experiment [14]. NEXT
collaboration is trying to identify the nature of neutrino, whether it is a
Majorana fermion or not, with the observation of $0\nu\beta\beta$
(Neutrinoless Double-Beta Decay) of 136Xe, with Qββ = 2.5 MeV. The detector is
a time projection chamber filled with xenon gas at pressure (7-15 bar), and
two separated detection planes: the energy plane - which is used to measure
the energy of events with PhotoMultiplier Tubes (PMT) with energy resolution
(ER) $<1\%$, and the tracking plane - which is used to track the electrons in
the gas with Silicon photomultipliers (SiPM). The main sources of background
to this experiment are the decays of two isotopes: 214Bi (2.447 MeV,
intensity: 1.57%) and 208Tl (2.614 MeV, intensity: 100%) - as shown in Figure
1, with gammas very close to Qββ.

An external Lead Castle (with 200 mm thickness) was built to shield the
detector from the radioactive gamma background of the laboratory [15]. At the
same time, a system to flush with ATEKO-air was developed. Inside the Castle a
diffusor with 8 air outputs (each one with 8 horizontal holes and 1 vertical)
was mounted to flush the detector with ATEKO-air (see below).

###  V.1 Firsts Tests of the Castle

In 2014, before the RAS and the installation of NEXT-White detector and the
diffusor, the initial plan was to reduce the Radon background inside the
Castle by building it as air-tight as possible and flowing a small volume of
N2 inside. To evaluate this design, several tests (from 29/10/2014 to
12/02/2015) [16] were done with a high pressure N2 bottle, changing the flow
and purging between measurements. These tests were made with the Castle
completely built, with all the joints in place but before placing the vessel
of NEXT-White on the pedestal. Therefore, the empty holes for the pipes of the
Castle were covered with High Density Polyethylene (PE-500).

Two different detectors were placed inside the Castle for these measurements:
one was an AlphaGuard Saphimo P2000 and the other was a 3” $\times$ 3” NaI(Tl)
detector. The NaI(Tl) instrumented crystal is a low background detector that
was connected to a Canberra 2005 preamplifier, a Tennelec linear amplifier and
a Canberra 8701 ADC, and finally read by an Arduino board. The rate measured
with the NaI(Tl) detector is shown in Figure 10. During these days, the Rn
activity in Hall A was in the range of 60 $-$ 80 Bq/m3.

To evaluate the contribution of the Castle, different setups were prepared:

  1. 1.

_Castle open_. This measurement was taken before closing the Castle to have a
reference value of the event rate. With the Castle open, the space between
both sides of the Castle is 2.9 m, therefore it was only partially shielded
from the gamma background coming from the laboratory. This measurement is not
shown in Figure 10.

  2. 2.

_Castle closed_ , drawn in blue in Figure 10. Measurement done after closing
the Castle.

  3. 3.

_Better closed Castle_ , drawn in red. Measurement done after improving the
air-tightness with additional joints, blocking the holes, etc.

  4. 4.

_After N 2 purge_, drawn in yellow. A purge was done with N2 with a flow of
1800 l/h for 7 hours to remove the Rn inside the Castle.

  5. 5.

_N 2 purge + flux 180 l/h_, drawn in green. A second purge was made but, after
this, a constant flux of 180 l/h was injected into the Castle.

  6. 6.

_Without N 2 flux_, drawn in violet. Measurement done after stopping the
constant flow of N2 in setup 5.

  7. 7.

_N 2 purge + flux 900 l/h_, drawn in brown. Same conditions as in setup 5 but
with a larger flux of 900 l/h.

  8. 8.

_Without N 2 flux_, drawn in turquoise. Same as in setup 6, measurement made
after stopping the N2 flux.

The results of these measurements are presented in Figure 10 and Table II. In
the Figure, NaI(Tl) total rate as function of time for different tests (in
different colors) are presented. In the third column of the table the average
rate for each test is calculated. In the fourth column the Radon activity
measured in short time windows for each test is shown.

Figure 10: _NaI(Tl) total rate as a function of time for different tests: blue
\- Castle closed; red \- Castle closed with improved tightness; yellow \-
Castle closed with 7h N2 purge at 1800 l/h; green \- Castle closed with N2
purge + constant N2 flux 180 l/h; violet \- Castle closed without N2 flux;
brown \- Castle closed with N2 purge + N2 flux 900 l/h; turquoise \- Castle
closed without N2 flux._ Table II:  _Measurements of the contribution of the
NEXT Castle in different tests._

| Setup | Rate with NaI (Hz) | Activity with AlphaGuard (Bq/m3)⋆
---|---|---|---
1 | Castle open | $59.56\pm 0.01$ |  $79\pm 28$
2 | Closed Castle | $1.089\pm 0.001$ | $79\pm 28$
3 | Better closed Castle | $0.694\pm 0.002$ | $30\pm 11$
4 |  After N2 purge | $0.658\pm 0.001$ | $30\pm 12$
5 |  N2 purge + flux 180 l/h | $0.600\pm 0.001$ | $22\pm 9$
6 |  Without N2 flux | $0.638\pm 0.001$ | $26\pm 10$
7 |  N2 purge + flux 900 l/h | $0.350\pm 0.002$ | $4\pm 3$
8 |  Without N2 flux | $0.894\pm 0.002$ | $47\pm 15$

⋆The AlphaGuard measurements were very short, only to obtain the order of
magnitude.

In setup 7, we observe a large background reduction. But for this measurement
the AlphaGuard detector is at its limit of sensitivity and the NaI(Tl) could
be contaminated by gammas from other sources. Therefore, the use of Radon-free
gas and more precise detectors are needed to improve the measurement.

###  V.2 Connection of NEXT to RAS

fter the installation of the RAS and the ERM, the possibility of a cheaper and
Rn-free air produced at LSC was the best option. Rn-free air is produced at
LSC and can be precisely measured with ERM. Additionally, more flexible safety
protocols around the Castle can be followed because there is no risk of
suffocation. The connection between the RAS and NEXT can be divided into three
different sections: Part I - LSC pipes system, Part II - the NEXT pipes
outside the Castle, and Part III - the NEXT pipes inside the Castle.

####  V.2.1 Description of Part I - the LSC pipe system

NEXT experiment and the RAS are in opposite parts of the Hall A, separated by
about 60 meters. Therefore, a pipe crossing the Hall A is used to deliver the
air. The installation is made of AISI-316 Stainless Steel pipe with
d$=4^{\prime\prime}$ (101,6 mm), welded, minimizing the number of joints. The
length of this pipe is 59 m. All joints are using flat flanges, according to
norm EN-1092-1 Type 1 PN-2.5. These flanges use rubber elastomeric gaskets.
For the air distribution, two manual ball valves are mounted at the outlet of
the RAS. In parallel to this installation, there is a pipe to return the air
from NEXT Castle to the ERM with d$=1^{\prime\prime}$ (25,4 mm) and made of
AISI-316 Stainless Steel, completely welded. This pipe has a length of 59
meters and has unions with threaded fittings, according to norm DIN-2999.

####  V.2.2 Description of Part II - the NEXT experiment pipe system

The system consists of a pipe with diameter d$=$1” 1/2 (38.1 mm) of AISI-316
Stainless Steel and several flexible pipes with d = 40 or 50 mm of PVC
(SPRINGVIN IBERFLEX). Pressed joints and threaded joints (type Pressfitting,
INOXPRESS) are used to connect these pipes (see Figure 11). All these joints
are using elastomeric gaskets of EPDM. For air distribution, several ball
valves are employed. We used flexible pipes to allow the opening of the
external Lead Castle and best suited to seismic vibrations affecting the
installation.

The NEXT pipe system includes several gauges:

  1. 1.

A flow meter Produal IVL10N with two output signals (for ventilation and air
conditioning). The signals correspond to air flow velocity and temperature
inside the air duct.

  2. 2.

A differential pressure sensor WIKA Model A2G-50 (for ventilation and air
conditioning). This sensor measures the air pressure at three different points
of the installation using solenoid valves:

a) the pressure in the Rn-free air inlet line,

b) the pressure in the pipe entering in the NEXT Castle and,

c) the pressure inside the Castle, around the detector.

  3. 3.

A manual flow-control valve to control the air flow to the Castle.

  4. 4.

Several manual ball valves located in different ’bypasses’, installed for
tests purposes for the RAS and the ERM.

  5. 5.

The system is monitored by an Arduino ARDBOX 20, from Industrial Shields.

####  V.2.3 Description of Part III - the diffusor, the detector and the
Castle

The air diffusor is placed inside the Castle, above the NEXT detector. This
diffusor is designed to homogeneously distribute the ATEKO-air inside the
Castle and displace the normal air (see Figure 12). In this Figure, the air
flow injected by the diffusor is shown in light blue. This diffusor is
designed to be used for both NEXT-White and NEXT100 detectors.

Figure 11: _Lateral section of the pressed joints and threaded joints,
pressfitting INOXPRES_ Figure 12: _Side view of the Rn-free air diffusor, the
Castle and the NEXT100 detector._

We show an upper cut (without the roof of the Castle) of the diffusor and the
NEXT-100 vessel in Figure 13. The flows of injected air from the 8 tubes of
the diffusor were marked with blue circles, above the detector. The Castle (in
red) is divided into two mobile parts. Both sides are independent and can be
moved to get access to the detector. For this purpose, a system with rails,
wagon wheels, and two electric motors to open and close the Castle was
implemented.

Figure 13: _Top view of the closed Castle with a scheme of the distribution of
the Rn-free air._

The Castle is shown with the right side opened in Figure 14 , where five of
the ten pipes coming from the RAS can be seen. The ten pipes (DN-100) are
crossing the two mobile parts of the lead of the Castle. To improve the Castle
airtightness and reduce the gamma background around the detector, special lead
bricks were machined to perfectly seal the space around the pipes. With these
bricks in place, the Castle can be opened and closed without manually removing
any other part of the shielding. There are foam fillings in all the joints
between the two mobile sides of the Castle and there is a bubble joint in the
union between the pedestal and the two mobile parts. All these joints are
necessary to keep the Castle air-tight.

Figure 14: _NEXT detector. Details of the connection system with the ATEKO
machine._ Figure 15: _Diffusor detail: 8 perimetral holes and 1 central, all
of them of diameter d $=$5 mm._

A closer view on a diffusor is shown in Figure 15. It has 8 perimetral holes
and 1 central, all of them of diameter d$=$5 mm. Radon tends to accumulate
above the pedestal. For this reason, these diffusor tubes are designed to
displace it using a large ATEKO-air flow injection. The air will escape from
the Castle through the external perimeter of the pedestal and also through the
small holes between the pipes and the lead (small leaks).

###  V.3 Tests of the pipes and the Castle

Due to the large distance between the RAS and the ERM, long pipes were needed:
pipes from the LSC setup are 59 m long and the ones from setup NEXT are 8
meters long. Considering also the return line, the total distance is 134 m. To
evaluate as precisely as possible the radon contribution of the different
parts of the system, 3 different tests were performed (see Figure 16 and Table
III). It is important to evaluate the contribution of all parts because some
pressed tubes were used instead of welded stainless steel pipes. Pressed tubes
are cheaper and easier to mount.

Figure 16: _Paths used for the three different measurements of Rn activity_

Test-1 (Part I - path marked in yellow in Figure 16) takes the ATEKO-air and
crosses all the Hall A and returns to the ERM to measure the Rn activity of
the air. To isolate this circuit, AV1 bypass valve was used. The total length
of this circuit is 118 m.

Test-2 (Part I and Part II - paths marked in yellow and orange in Figure 16)
includes all pipes but not entering inside the Castle. In this case, AV1 was
closed and AV5 opened. The total length of this circuit is 132 m.

Test-3 (Part I, Part II and Part III - paths marked in yellow, orange and
green in Figure 16) uses the final setup used in NEXT. The ATEKO-air enters in
the Castle and, through the diffusors, baths NEXT-White detector. To complete
the circuit, a small open pipe at the base of the pedestal takes the air into
the return line. The open pipe is placed where the Rn accumulates with the air
flowing (lower part of the Castle). With this setup, there is no overpressure
so we use a pump to force the circulation of the air towards the ERM. AV1 and
AV5 are closed. The total length of this circuit is 134 m.

Table III:  _Activity Rn measured with ERM for the Tests._ Test-1 | Test-2 | Test-3 - I | Test-3 - II
---|---|---|---
$\leq 1.3$ mBq/m3 |  $\leq 4.3$ mBq/m3 | 45.0 mBq/m3 | 31.0 mBq/m3

Two levels of flow at the entrance of the Castle were used in Test-3. Test-3-I
(conditions similar as in Test-1 and Test-2), was performed with a flow of
$\sim$ 400 l/m. For Test-3-II, a larger flow of $\sim$ 550 l/min was (see
Figure 16) used. The Rn-free air significantly reduces the amount of radon
(factor larger than 1000) in the neighborhood of the NEXT-100 vessel, a number
that varies with the air flow.

Figure 17: _Daily Radon activity vs Background rate in NEXT-White[17]._ Figure
18: _Evolution of the total background in NEXT-White detector. The vertical
dashed red lines indicate the beginning of each run[17]._

Before the ATEKO-air diffusor installation was completed, a study of the
influence of the Rn concentration outside the detector (between 60 and 100
Bq/m3 \- measured with an AlphaGuard detector) on NEXT background was
performed with the NEXT-White detector (see Figure 17) [17]. A linear
correlation may be used to estimate the background rate in NEXT detector and
the Rn concentration outside the vessel. Extrapolating the red dashed line to
a Rn-free scenario, the expected background rate was $3.97\pm 0.46$ mHz.
During the background run of NEXT-White, data has been taken first without
ATEKO-air (run IVa) and later with ATEKO-air flowing around the detector (run
IVb). Without ATEKO-air, the background rate was $8.00\pm 0.05$ (stat) $\pm
0.07$ (sys) mHz, and with ATEKO-air was $3.90\pm 0.05$ (stat) $\pm 0.04$ (sys)
mHz (see Figure 18) [17]. The result of run IVb and the previous extrapolation
are in a very good agreement. In Run IVc an additionally second inner lead
shield was mounted. In this run the background rate was reduced to $2.78\pm
0.03$ (stat) $\pm 0.03$ (sys) mHz.

##  VI ATEKO-AIR TO ULBS

The Ultra-Low Background Service (ULBS), working since 2010 in Hall C of LSC
(Figure 20), is offering a high-quality screening facility to experiments [4].
At present, it is equipped with six 2 kg p-type coaxial High Purity Germanium
(HPGe) detectors with $\sim 100\%$ relative efficiency, shielded with 20 cm of
lead with a low contamination in 210Pb ($<30$ mBq/kg). An internal 10 cm of
OFHC (Oxygen-Free High thermal Conductivity) copper layer completes the
shielding. The ULBS carries out mainly radio-purity assay for experiments
running at LSC and collaborations [18], [19], [20], [21] and also contributes
to SK-Gd [22] and HK [23] experiments in Kamioka.

Figure 19: _ULBS laboratory in Hall C of LSC._

Figure 20: _Sample volume inside the Cu shielding._ Figure 21: _Schematic of
HPGe positioning in Hall C. In red, the installation to supply ATEKO-Air to
each detector._ Figure 22: _ATEKO-Air main line in
Hall C._ Figure 23: _ATEKO-Air Rotameter with valve
to measure and regulate air flow rate._

Long measurements (about 30 days) are necessary to reach sensitivity levels of
1 mBq/kg or less, with the condition that the Radon contained in the air
inside the HPGe-detector shielding is at the level of 1 mBq/m3 or less. For
this purpose, each detector has an extra layer of shielding made of
methacrylate that externally surrounds the lead shielding. To impede the
exterior air (and the Rn) from entering inside the shielding, a slight
overpressure is created inside the copper shielding. The inner volume
available for sample measurement (the inside of the Cu shielding) has the
geometry of a cube with side 350 mm (see Figure 20). This gives a volume of
$\sim 43$ l.

Two systems are used to reduce the Rn concentration inside the HPGe-detector
copper shielding. The first system uses the nitrogen that is evaporating from
the detector’s dewar. Each HPGe-detector in LSC is equipped with a 30 l dewar
for LN2 necessary for the detector operation. LN2 has to be refilled each
week. Using a 6 mm diameter Teflon tube, we flush continuously $\sim 54$ l/h
inside the detector the N2 gas which is evaporating from the dewar. This value
was obtained by measuring (with a graded stick) the height of LN2 and
calculate the evaporated gas considering that each liter of LN2 will produce
$\sim 696$ liters of gaseous N2. Before the RAS, this setup was the only anti-
Radon system.

Table IV: _Background counts in the 2 setups: 2016-setup with a flux of N 2 from dewar evaporation of 54L/h; 2021-setup with a flux of 274 l/h made by combined N2 from dewar evaporation and ATEKO-Air._ | Flux | Gas | Int. rate [40 - 2700 keV] | Int. rate [609.32 keV peak]
---|---|---|---|---
| [l/h] |  | [cts/kg/day] | [cts/kg/day]
2016 setup | 54 | N2 | 165.3 | 2.9
2021 setup | 274 | N2+Air | 141.8 | 0.4

The second system, using the RAS, reduces even more the total background of
the HPGe detectors. A fixed installation was specially built in 2019 to flow
ATEKO-air inside the shielding of the detectors (Figure 21). We did some tests
and we concluded that there is no difference in the detector’s background rate
when using the LN2 evaporation or ATEKO-air if the flow inside the shielding
has the same value. Currently, the flow is 220 l/h in each detector. This flow
rate can be regulated with a valve for each detector and the flux is measured
with a rotameter (see Figures 22 and 23).

To optimize the use of the ATEKO-air and obtain a proper Radon reduction we
are using both systems. The total flux (ATEKO-air + N2) flushed inside the
detector is $\sim 274$ l/h so the air is changed more than 6 times per hour in
the sample volume.

To show the background reduction, we compare (Table IV and Figure 24) the
rates of GeOroel (one of the best HPGe’s of LSC) with the old (2016) and the
current setup, i.e., N2 evaporated from the dewar versus ATEKO-air injected
and N2 evaporated from the dewar.

Figure 24: _GeOroel background comparison, 214Bi 609.32 keV peak of reduction.
In blue 2016 setup vs. in red 2021-setup._

##  VII ATEKO-AIR TO CROSS EXPERIMENT

The goal of the Cryogenic Rare-event Observatory with Surface Sensitivity
(CROSS) [24], [25], [26] is the development of a technology capable of
investigating lepton number violation and the nature of neutrino with
unprecedented sensitivity, by searching for neutrinoless double beta decay
$0\nu\beta\beta$ of two promising isotopes (100Mo and 130Te) with the
bolometric approach. The choices of the candidates and of the compounds for
CROSS are based on years of development of the bolometric search for
$0\nu\beta\beta$ decay projects: MIBETA, Cuoricino, CUORE, LUCIFER, CUPID-0,
LUMINEU and CUPID-Mo (see [24] and bibliography inside). The baseline solution
is background reduction by the scintillating-bolometer technology, as proposed
in the CUPID project [27], [28]. CROSS can provide an adequate background
abatement with a major simplification of the detector structure and of the
readout.

A dilution refrigerator with an experimental volume of about $\sim 150$ l was
installed in April 2019 in the LSC in the framework of the CROSS project. The
CROSS key idea is to provide the bolometric detection technique, ideally
tailored to the study of this rare nuclear transition as it features high
energy resolution, large efficiency and wide flexibility in the detector
material choice –- with an additional decisive characteristic: an effective
pulse-shape-discrimination (PSD) capability, enabling the rejection of events
from surface radioactive impurities and other background-inducing phenomena.
CROSS is planning to install a first demonstrator of the CROSS technology in
this cryogenic set-up [24]. It will consist of 32 Li2MoO4 crystals grown with
molybdenum enriched in 100Mo at $>95\%$ level with CROSS technology [25]. The
region of interest (ROI) is around 3034 keV. Each crystal is a cube with 45 mm
side, for a mass of 0.28 kg. This new detector will pave the way to bolometric
experiments with low background levels (see Table V [24]) to make possible
future large searches penetrating in prospects the normal hierarchy of the
neutrino masses.

Figure 25: _CROSS Anti-Radon Shield._ Table V:  _Sensitivity of the CROSS demonstrator to be operated in the cryogenic facility of the Canfranc underground laboratory, under two different hypotheses of background level. The efficiency is 75%, compatible with the crystal size of each element. The interval of limits on the effective Majorana neutrino mass $m_{\beta\beta}$ accounts for a recent compilation of nuclear-matrix-element calculations [24]._ Background | Live | Background | Feldman-Cousins | Half-life | mββ
---|---|---|---|---|---
level | time | counts | count limit | limit [y] | limits [meV]
[counts/(keV kg y)] | [y] | in ROI | (90% C.L.) | (90% C.L.) | (90% C.L.)
$10^{-2}$ | 2 | 1.40 | 3.6 | $8.5\times 10^{24}$ | 124–222
$10^{-3}$ | 2 | 0.14 | 2.5 | $1.2\times 10^{25}$ | 103–185
$10^{-2}$ | 5 | 3.60 | 4.6 | $1.7\times 10^{25}$ | 88–159
$10^{-3}$ | 5 | 0.36 | 2.7 | $2.8\times 10^{25}$ | 68–122

To reach such low levels of background all external contributions must be
mitigated. One of these background sources [24] is the Rn in the air outside
the experiment ($69.0\pm 0.3$) Bq/m3 as we shown above. To remove this
background, the system is similar to the one used in the HPGe detectors: an
extra tight shielding made of stainless steel was constructed to surround the
detector’s cylindrical lead shielding. ATEKO-air is inserted inside this last
layer to create a slight overpressure and impede the external air that
contains Radon to enter and produce background.

The shielding design is a cylinder made of a 1 mm Stainless Steel sheet with
internal diameter D = 990 mm and 1200 mm hight (see Figure 25). The shield is
made of several components that can be easily assembled. Silicone gaskets and
PTFE are used to maintain the ensemble tight. As the free volume that remains
inside this anti-Radon shield is relatively small ($\sim 45$ l), a flux of 280
l/h of ATEKO-air is sufficient to remove the Rn background to the order of 1
mBq/m3. The ATEKO-air installation is very similar to that installed in ULBS
(Hall C), a Rotameter with a valve will be used to regulate the Rn-free air
flux inside the detector. The shield was mounted in the fall 2021 and will be
tested in the following CROSS run starting in December 2021.

##  VIII CURRENT PLANS

The Rn-free air line became a much needed service at the underground lab and
will be further exploited in the near future, with new science and technology
projects.

NEXT-100, an upgraded version of NEXT-White, consists of a larger vessel TPC
filled with 100 kg of 136Xe-enriched Xe at 15 bar. Some improvements to the
NEXT Castle and the corresponding ATEKO-air input system are in progress:
remove the painting to reduce radioactive background and improve air sealing.
Also, because a larger TPC will be mounted (lower volume of air inside the
Castle) we can expect an important reduction of the radioactive background.

The Radon-free air supply is also essential for the Copper Electroforming
Services (CES) [29] recently installed in the LSC Clean Room. A major program
of improving the service was done recently to obtain the highest radiopurity
of the copper produced in Canfranc, currently tested with components for DAMIC
experiment [30], and for additive printing. In the near future, it is planned
to test the Radon-free air as an inert gas inside the electrolytic bath
instead of nitrogen gas.

The Rn-free air from RAS is necessary in the LSC microbiology and molecular
biology laboratory. Currently, five experiments have been approved to start
their works underground. These experiments are focused on studies of
phenotypic and molecular adaptations of biological models, such as
microorganisms or small multicellular eukaryotic organisms in low radiation
background environment. The RAS will be used to minimize the Rn environmental
background, as done in the physics experiments, to fully monitor the
background conditions in the experiments.

##  IX CONCLUSIONS

The combination of Underground Laboratories and Radon Abatement Systems
guaranties an ideal space to study very low background physics. The LSC, with
the addition of this RAS, can offer 5 orders of magnitude of cosmic rays
suppression and about $1$ mBq/m3 of 222Rn activity in air.

This reduction has been demonstrated in several types of detectors. In
particular, thanks to a dedicated pipe able to deliver Rn-free air, NEXT-NEW
experiment has reduced the contribution of radon to its background budget from
50% to a negligible level. For HPGe detectors, the addition of ATEKO-air to
the air flow around the detector has significantly reduced the number of
counts in the peaks in the lower part of the 238U chain.

The use of RAS in the underground lab is continuously growing and will be
essential in the coming months and years to further improve the radioactive
background environment of experiments and technologies, particularly in the
growing activities in biology, where air can not be replaced by nitrogen.

##  X ACKNOWLEDGMENTS

This work was supported in part by the European Regional Development Fund
(ERDF), corresponding to the 2013-2016 Spanish Scientific and Innovation
Research Program, grants No. CPEE15-EE-3829 and No. CPEE13-4E-2646.

This work was supported in part by the Polish National Science Centre (NCN),
grant No. UMO-2020/37/B/ST2/03905 and the Polish Ministry of Education and
Science grant No. DIR/WK/2018/08.

Laboratorio Subterráneo de Canfranc (LSC) is a Spanish Unique Science and
Technology Public Research Institution (ICTS) granted by the Spanish Ministry
of Science and Innovation, The Regional Government of Aragon and the
University of Zaragoza.

## References

  * [1] Bettini A.; New underground laboratories: Europe, Asia and the Americas Physics of Dark Universe 2014, Volume 4, 36-40.
  * [2] Wójcik, M.; Zuzel, G.; Simgen, H. Review of high-sensitivity Radon studies, International Journal of Modern Physics A 2017, Volume 32, Issue 30, id. 1743004.
  * [3] LSC Website. Available online:
https://lsc-canfranc.es/wp-content/uploads/2019/03/2017_EN.pdf
(accessed on 20/01/2022).

  * [4] Bandac, I; et al. Ultra-low background and environmental measurements at Laboratorio Subterráneo de Canfranc (LSC) Applied Radiation and Isotopes 2017, Vol 126, 127-129.
  * [5] Arvela, H.; Holmgren, O.; Hänninen, P. Effect of soil moisture on seasonal variation in indoor radon concentration: modelling and measurements in 362 Finnish houses, Radiation Protection Dosimetry 2016, Vol. 168, Issue 2, 277-290.
  * [6] Shweikani, R.; Giaddui, T.G.; Durrani, S.A. The effect of soil parameters on the radon concentration values in the environment, Radiation Measurements 1995, Vol. 25, Issues 1-4, 581-584.
  * [7] Maeng, Y.; Busenitz, J.; Piepke, A. A new method for evaluating the effectiveness of plastic packaging against radon penetration, Applied Radiation and Isotopes 2020, Vol. 156, 108963 [arXiv:1903.02643].
  * [8] Mamedov, F., C̆ermák, P.; Smolek, K. S̆tekl, I. Measurement of radon diffusion through shielding foils for the SuperNEMO experiment, JINST 2011, Vol. 6, C01068.
  * [9] Bandac, I; et al. Radón y radiación ambiental en el Laboratorio Subterráneo de Canfranc (LSC), Radioprotección (SEPR) 2014, 77, Vol. XXI, P24-29.
  * [10] Pelczar, K.; Zuzel, G.; Wójcik, M; Pocar, A; Ianni, A. An online radon monitor for low-background detector assembly facilities, Eur. Phys. J. C 2021, 81:86.
  * [11] Hodák, R.; et al Characterization and long-term performance of Radon Trapping Facility operating at the Modane Underground Laboratory, Journal of Physics G: Nuclear and Particle Physics 2019, 46, 115105.
  * [12] Lee, M.H.; et al. Radioassay and Purification for Experiments at Y2L and Yemilab in Korea, Journal of Physics: Conference Series 2020, TAUP 2019, 1468, 012249.
  * [13] ATEKO a.s. Website. Available online:
https://www.ateko.cz/media/cache/file/25/ATEKO_Radon_Removal_Systems_2020.pdf
(accessed on 26/01/2022).

  * [14] Monrabal, F; et al. (NEXT Collaboration) The Next White (NEW) Detector JINST 2018, 13, P12010, [arXiv:1804.02409].
  * [15] Martín-Albo, J.; et al. (NEXT Collaboration) Sensitivity of NEXT-100 to neutrinoless double beta decay, J. High Energ. Phys. 2016, 159 [arXiv:1701.02697].
  * [16] Cebrián, S.; et al. (NEXT Collaboration) Radon and material radiopurity assessment for the NEXT double beta decay experiment, AIP Conf. Proc. 2015, 1672 060002 [arXiv:1505.07052].
  * [17] Novella, P.; et al. (NEXT Collaboration) Radiogenic backgrounds in the NEXT double beta decay experiment, J. High Energ. Phys. 2019, 51 [arXiv:1905.13625].
  * [18] Cebrian, S.; et al. (NEXT Collaboration) Radiopurity assessment of the energy readout for the NEXT double beta decay experiment, JINST 2017, 12, T08003 [arXiv:1706.06012].
  * [19] Dafni, T.; et al. (NEXT Collaboration) Results of the material screening program of the NEXT experiment, Nuclear and Particle Physics Proceedings 2016, 273-275, 2666-2668 [arXiv:1411.1222].
  * [20] Tzika, F.; et al. Coordinate underground measurements of gamma-ray emitting radionuclides for plasma physics research, Applied Radiation and Isotopes 2017, 126, 121-126.
  * [21] Picado, E.; et al. Radiopurity Study of an Encapsulated CeBr3 crystal, JPS Conf. Proc. 2015, 6, 030133.
  * [22] Marti Ll.; et al, Evaluation of gadolinium’s action on water Cherenkov detector systems with EGADS, Nucl. Instrum. Methods, A 2020, 959, 163549
  * [23] Abe K.; et al (Hyper-Kamiokande Proto-Collaboration), Hyper-Kamiokande Design Report, [arXiv:1805.04163].
  * [24] Bandac, I.C.; et al. (CROSS Collaboration) The $0\nu 2\beta$-decay CROSS experiment: preliminary results and prospects, JHEP 2020, 18 [arXiv:1906.10233].
  * [25] Bandac, I.C.; et al. (CROSS Collaboration) Phonon-mediated crystal detectors with metallic film coating capable of rejecting $\alpha$ and $\beta$ events induced by surface radioactivity, Applied Physics Letters 2021, 118, 184105 [arXiv:2103.07181].
  * [26] Armatol, A.; et al. (CROSS Collaboration) A CUPID Li2 100MoO4 scintillating bolometer tested in the CROSS underground facility, JINST 2021, 16, P02037 [arXiv:2011.13806].
  * [27] CUPID Collaboration; CUPID pre-CDR 2019 [arXiv:1907.09376].
  * [28] CUPID Collaboration;CUORE (Cryogenic Underground Observatory for Rare Events) Upgrade with Particle IDentification 2015 [arXiv:1504.03599].
  * [29] Borjabad, S.; et al. Copper electroforming service at Laboratorio Subteráneo de Canfranc (LSC), AIP Conference Proceedings 2018, 1921, 020001.
  * [30] DAMIC-M Website. Available online:
https://damic.uchicago.edu/
(accessed on 25/01/2022).


A preliminary version of this work was published in the proceedings of
FSTTCS’2014 [CFH14].

# Playing Safe, Ten Years Later

Thomas Colcombet0000-0001-6529-6963  CNRS, IRIF, Université de Paris, Paris,
France  ,  Nathanaël Fijalkow0000-0002-6576-4680  CNRS, LaBRI, Bordeaux,
France  and  Florian Horn  CNRS, IRIF, Université de Paris, Paris, France

###### Abstract.

We consider two-player games over graphs and give tight bounds on the memory
size of strategies ensuring safety objectives. More specifically, we show that
the minimal number of memory states of a strategy ensuring a safety objective
is given by the size of the maximal antichain of left quotients with respect
to language inclusion. This result holds for all safety objectives without any
regularity assumptions. We give several applications of this general
principle. In particular, we characterize the exact memory requirements for
the opponent in generalized reachability games, and we prove the existence of
positional strategies in games with counters.

###### Key words and phrases:

Games on graphs, Memory

##  1\. Introduction

Graphs games provide a mathematical framework to model reactive systems (we
refer to [GTW02] for a survey on the topic). We focus here on the Synthesis
Problem to motivate the problem we consider, which is to characterize the
amount of memory required in games with safety objectives.

The Synthesis Problem. The inputs of the Synthesis Problem are a system and a
specification. The expected output is a controller for the system, that
ensures the specification.

We describe here an approach to solve the Synthesis Problem through Game
Theory. We model the system as a graph, whose vertices represent states and
edges represent transitions. Its evolution consists in interactions between a
controller and an environment, which is turned into a game on the graph
between two players, Eve and Adam. If in a given state, the controller can
choose the evolution of the system, then the corresponding vertex is
controlled by Eve. If the system evolves in an uncertain way, we consider the
worst-case scenario, where Adam controls those states.

A pebble is initially placed on the vertex representing the initial state of
the system, then Eve and Adam move this pebble along the edges. The sequence
built describes a run of the system: Eve tries to ensure that it satisfies the
specification.

So, in order to synthesize a controller, we are interested in whether Eve can
ensure this objective and what resources she needs. In particular, the most
salient question is: what is the size of a minimal controller satisfying the
specification? Since a controller is here given by a strategy for Eve, this is
equivalent to the following question: what is the minimal amount of memory
used by a winning strategy?

The following diagram shows the correspondence between the notions from the
Synthesis Problem (left-hand side) and the game-theoretical notions (right-
hand side).

$\underbrace{\mathbb{S}}_{\textrm{system}},\underbrace{\mathcal{C}}_{\textrm{controller}}\models\underbrace{\Phi}_{\textrm{specification}}\qquad\Longleftrightarrow\qquad\underbrace{\mathcal{A}}_{\textrm{arena
(graph)}},\underbrace{\sigma}_{\textrm{strategy}}\models\underbrace{W}_{\textrm{objective}}$

Safety Specifications. Since we consider non-terminating sequences, a
specification is given by a language of infinite words. Of special interest
are the specifications asserting that “nothing bad” ever happens; such
specifications are called safety specifications. A safety specification is
induced by a (possibly infinite and non-regular) set of bad prefixes $P$, and
the specification is met by a run if no prefixes belong to $P$.

Although quite simple, the safety specifications proved useful in both theory
and practice, and are actively studied (we refer to [Kup14] for a survey).

Our contribution. In this paper, we show the following general principle:

For a safety winning objective $W$, the minimal number of memory states of a
winning strategy is exactly the cardinal of the maximal antichain of left
quotients of $W$.

We refer to Section 4 for the missing definitions. Note that this result holds
for all safety winning objectives, without any regularity assumption. The
characterisation above holds for graphs with finite degree, however we can
state and prove a variant lifting this assumption, but assuming that the set
of left quotients is well founded with respect to inclusion. We state our main
results in Section 3, and prove them in Section 4. We give several examples
and applications in Section 5. For instance, it allows to characterize the
memory requirements for the opponent in generalized reachability games, and to
prove the existence of positional strategies in games with counters. This
journal version additionally discusses related works in Section 6, many of
them posterior to the publication of the conference version of this article
[CFH14] in 2014.

##  2\. Definitions

The games we consider are played on an _arena_
$\mathcal{A}=(V,(V_{\exists},V_{\forall}),E,c)$, consisting of a (finite or
infinite) graph $(V,E)$, a partition $(V_{\exists},V_{\forall})$ of the vertex
set $V$: a vertex in $V_{\exists}$ belongs to Eve and in $V_{\forall}$ to
Adam, and a coloring function $c:E\to A$ mapping edges to a color from a
finite alphabet $A$. When drawing arenas, we will use circles for vertices
owned by Eve and squares for those owned by Adam. Throughout this paper, we
make the cosmetic assumption that graphs do not have dead-ends: for every
vertex $v\in V$, there exists an edge $(v,v^{\prime})\in E$.

Game. A _play_ $\pi$ is an infinite word of edges $e_{0}\cdot e_{1}\cdots$
that are consecutive: for all $i$, $e_{i}=(\\_,v)\in E$ and
$e_{i+1}=(v,\\_)\in E$ for some $v\in V$. The prefix of length $k$ of $\pi$ is
denoted $\pi_{k}$. A play $\pi$ induces an infinite sequence of colors
$c(\pi)$, obtaining by applying the coloring function $c$ component-wise. We
define _winning objectives_ for a player by giving a set of infinite sequences
of colors $W\subseteq A^{\omega}$. As we are interested in zero-sum games,
i.e. where the winning objectives of the two players are opposite, if the
winning objective for Eve is $W$, then the winning objective for Adam is
$A^{\omega}\setminus W$. A _game_ is a couple $\mathcal{G}=(\mathcal{A},W)$
where $\mathcal{A}$ is an arena and $W$ a winning objective.

Strategy. A _strategy_ for a player is a function that prescribes, given a
finite history of the play, the next move. Formally, a strategy for Eve is a
function $\sigma:E^{*}\cdot V_{\exists}\to E$ such that for all $\pi\in E^{*}$
and $v\in V_{\exists}$ we have $\sigma(\pi\cdot v)=(v,\\_)\in E$. Strategies
for Adam are defined similarly, and usually denoted $\tau$. Once a game
$\mathcal{G}=(\mathcal{A},W)$, a starting vertex $v_{0}$ and strategies
$\sigma$ for Eve and $\tau$ for Adam are fixed, there is a unique play
$\pi(v_{0},\sigma,\tau)$, which is said winning for Eve if its image by $c$
belongs to $W$.

A strategy $\sigma$ for Eve is _winning_ if for all strategies $\tau$ for
Adam, $\pi(q_{0},\sigma,\tau)$ is winning. We say that Eve wins the game
$\mathcal{G}$ from $v_{0}$ if she has a winning strategy from $v_{0}$, and
denote $\mathcal{W}_{E}(\mathcal{G})$ the set of vertices from where Eve wins;
we often say that $v\in\mathcal{W}_{E}(\mathcal{G})$ is winning. We define
similarly $\mathcal{W}_{A}(\mathcal{G})$ for Adam to be the set of vertices
from where Adam wins.

Memory. A _memory structure_ is a deterministic state machine that reads the
sequence of edges and abstracts its relevant informations into a memory state.
Formally, a memory structure $\mathcal{M}=(M,m_{0},\mu)$ for an arena consists
of a set $M$ of memory states, an initial memory state $m_{0}\in M$ and an
update function $\mu:M\times E\to M$. The update function takes as input the
current memory state and the chosen edge to compute the next memory state. It
can be extended to a function $\mu^{*}:E^{*}\to M$ by defining
$\mu^{*}(\varepsilon)=m_{0}$ and $\mu^{*}(\pi\cdot e)=\mu(\mu^{*}(\pi),e)$.
Given a memory structure $\mathcal{M}$ and a next-move function
$\nu:V_{\exists}\times M\to E$, we can define a strategy $\sigma$ for Eve by
$\sigma(\pi\cdot v)=\nu(v,\mu^{*}(\pi\cdot v))$. A strategy with memory
structure $\mathcal{M}$ has finite memory if $M$ is a finite set. It is
_memoryless_ , or _positional_ if $M$ is a singleton: it only depends on the
current vertex. Hence a memoryless strategy can be described as a function
$\sigma:V_{\exists}\to E$. We denote $\mathrm{mem}(\sigma)$ the number of
memory states used by the strategy $\sigma$.

An arena and a memory structure induce an expanded arena where the current
memory state is computed online. Formally, the arena
$\mathcal{A}=(V,(V_{\exists},V_{\forall}),E,c)$, the memory structure
$\mathcal{M}$ for $\mathcal{A}$ and a new coloring function
$c^{\prime}:E\times M\to A$ induce an expanded arena
$\mathcal{A}\times\mathcal{M}=(V\times M,(V_{\exists}\times
M,V_{\forall}\times M),E\times\mu,c^{\prime})$, where $E\times\mu$ is defined
by: $((v,m),(v^{\prime},m^{\prime}))\in E\times\mu$ if $(v,v^{\prime})\in E$
and $\mu(m,(v,v^{\prime}))=m^{\prime}$.

From a memoryless strategy in $\mathcal{A}\times\mathcal{M}$, we can build a
strategy in $\mathcal{A}$ using $\mathcal{M}$ as memory structure, which
behaves as the original strategy. This key observation will be used several
times in the paper.

##  3\. Statements of the Results

In this section, we consider a safety objective111To be defined in this
section. $W$ and compute the following quantity:

$\mathrm{mem}(W)\ \doteq\
\sup_{\begin{subarray}{c}\mathcal{G}=(\mathcal{A},W)\textrm{ game}\\\
v_{0}\textrm{ initial vertex}\end{subarray}}\
\inf_{\begin{subarray}{c}\sigma\textrm{ winning}\\\
\textrm{strategy}\end{subarray}}\ \mathrm{mem}(\sigma)\ .$

In words, $\mathrm{mem}(W)$ is the necessary and sufficient number of memory
states for constructing a winning strategy in games with objective $W$.
Equivalently:

  * •

upper bound: for all games $\mathcal{G}=(\mathcal{A},W)$, if Eve has a winning
strategy from an initial vertex $v_{0}$, then she has a winning strategy using
at most $\mathrm{mem}(W)$ memory states,

  * •

lower bound: there exists a game $\mathcal{G}=(\mathcal{A},W)$ and an initial
vertex $v_{0}$ where Eve has a winning strategy, but no winning strategy using
less than $\mathrm{mem}(W)$ memory states.

Note that we place no restrictions on the size of the games involved: they may
be infinite.

The reader with a background in game theory may be surprised, as it is well
known that “safety games are positionally determined”, implying that the
quantity above is constant equal to one. The subtlety here is that our setting
is (much) more general than the classical notion of safety games, as we
explain now.

Consider an arena $\mathcal{A}$: a safety condition is given by a subset
$B\subseteq E$ of forbidden edges, inducing the winning condition

$\\{\rho=a_{0}\cdot a_{1}\cdots\in E^{\omega}\mid\textrm{for all }i,\
a_{i}\notin B\\}\ .$

Let $A$ a set of colours. A safety objective is given by a subset $P\subseteq
A^{*}$ of forbidden prefixes of colors, inducing the winning objective

$\mathrm{Safe}(P)=\\{\rho=a_{0}\cdot a_{1}\cdots\in A^{\omega}\mid\textrm{for
all }i,\ a_{0}\cdot a_{1}\cdots a_{i}\notin P\\}\ .$

For each arena $\mathcal{A}$ equipped with a colouring function $c:E\to A$,
this induces the winning condition

$\\{\rho=a_{0}\cdot a_{1}\cdots\in E^{\omega}\mid c(\rho)=c(a_{0})\cdot
c(a_{1})\cdots\in\mathrm{Safe}(P)\\}.$

In other words, a condition is defined directly on an arena, while an
objective is defined independently of the arena on the sequence of colours and
induces a condition for each arena equipped with a colouring function.

######  Lemma 1 (Folklore).

Let $\mathcal{G}$ be a game with a safety condition, and $v_{0}$ an initial
vertex. If Eve has a winning strategy, then she has a positional winning
strategy.

Safety objectives form a very expressive class of objectives, as we will
demonstrate in Section 5.

The notion of safety objective originates from topological studies of the set
of infinite words: the safety objectives are the closed sets for the Cantor
topology, denoted $\Sigma_{1}$ in the corresponding Borel hierarchy.

Let us fix a safety objective $W=\mathrm{Safe}(P)$ induced by $P\subseteq
A^{*}$. Let $w\in A^{*}$, define its left quotient as:

$w^{-1}W=\\{\rho\in A^{\omega}\mid w\cdot\rho\in W\\}.$

We denote $\mathrm{Res}(W)$ the set of left quotients of $W$. We mention some
special left quotients: the initial one, $\varepsilon^{-1}W$ (equal to $W$),
and the empty one, obtained as $w^{-1}W$ for any $w\in P$. As a small abuse of
notations, from now on by “left quotient” we mean “non-empty left quotient of
$W$”.

From a left quotient $w^{-1}W$ and a letter $a\in A$, we define
$(w^{-1}W)\cdot a$ as $(w\cdot a)^{-1}W$: it is easy to check that this is
well defined (independent of the representant $w$ chosen). Recall that
$\mathrm{Res}(W)$ is finite if and only if $W$ is regular, and in such case it
can be used to describe the set of states of the minimal deterministic
automaton recognizing $W$.

Before stating our main results, we need some order-theoretic definitions. The
width of an ordered set $(E,\leq)$ is the cardinal of the maximal antichain of
$E$ with respect to $\leq$, i.e. the cardinal of the largest set of pairwise
incomparable elements. Recall that an antichan is a subset of $E$ such that
any two distinct elements are incomparable, and a chain is a subset of $E$
such that any two elements are comparable. We say that $(E,\leq)$ is well
founded if every chain contains a minimal element.

We write $\mathrm{mem}_{\textrm{fin-deg}}(W)$ for the quantity defined as
$\mathrm{mem}(W)$ but restricting to arenas of finite degree: for every
vertex, there are finitely many outgoing edges.

######  Theorem 1.

For all safety objectives $W$,

  * •

$\mathrm{mem}_{\textrm{fin-deg}}(W)$ is the width of
$(\mathrm{Res}(W),\subseteq)$.

  * •

if $(\mathrm{Res}(W),\subseteq)$ is well-founded (in particular if $W$ is
regular), then $\mathrm{mem}(W)$ is the width of
$(\mathrm{Res}(W),\subseteq)$.

An objective $W$ is half-positional if $\mathrm{mem}(W)=1$. In the case of
safety objectives, we obtain the following characterization:

######  Corollary 1.

For all safety objectives $W$, $W$ is half-positional over arenas of finite
degree if and only if the inclusion is a linear order over $\mathrm{Res}(W)$.

If furthermore $(\mathrm{Res}(W),\subseteq)$ is well-founded, then $W$ is
half-positional (over all arenas) if and only if the inclusion is a linear
order over $\mathrm{Res}(W)$.

The width has an equivalent formulation: thanks to Dilworth’s theorem, the
width of an ordered set $(E,\leq)$ is also the smallest number of chains
required to cover all elements. This point of view turned out fruitful in
further extensions of our results, see the related works section.

##  4\. Proofs

### A First Upper Bound

######  Lemma 2.

For all games $\mathcal{G}=(\mathcal{A},W)$, if Eve has a winning strategy
from an initial vertex $v_{0}$, then she has a winning strategy using at most
$|\mathrm{Res}(W)|$ memory states.

Consequently,

$\mathrm{mem}_{\textrm{fin-deg}}(W)\ \leq\ \mathrm{mem}(W)\ \leq\
|\mathrm{Res}(W)|\ .$

###### Proof.

We construct a memory structure $\mathcal{M}$, as follows:
$\mathcal{M}=(\mathrm{Res}(W),W,\nu)$, where $\nu(w^{-1}W,a)=(w^{-1}W)\cdot
a$. At any point in the game, the memory state computed by $\mathcal{M}$ is
the current left quotient. Let $\mathcal{A}$ be an arena. We construct the
expanded arena $\mathcal{A}\times\mathcal{M}$ equipped with the coloring
function $c^{\prime}:E\times\mathrm{Res}(W)\to\\{0,1\\}$ defined by:

$c^{\prime}(\\_,w^{-1}W)=\begin{cases}0&\textrm{ if }w^{-1}W=\emptyset\textrm{
(equivalently, }w\in P\textrm{)}\ ,\\\ 1&\textrm{ otherwise}\ .\end{cases}$

We attach to $\mathcal{A}\times\mathcal{M}$ the safety condition induced by
$B=\\{0\\}$, giving rise to the game
$\mathcal{G}\times\mathcal{M}=(\mathcal{A}\times\mathcal{M},\mathrm{Safe}(B))$.
First observe that by construction, the plays in
$\mathcal{A}\times\mathcal{M}$ are of the form
$(e_{0},c(e_{0})^{-1}W)\cdot(e_{1},c(e_{0}\cdot
e_{1})^{-1}W)\cdots(e_{k},c(e_{0}\cdot e_{1}\cdots e_{k})^{-1}W)$, so by
definition of $c^{\prime}$ a play is winning is $\mathcal{G}\times\mathcal{M}$
if and only if its projection (on the first component) is winning in
$\mathcal{G}$.

It follows that a winning strategy for Eve in $\mathcal{G}$ from $v_{0}$
induces a winning strategy in $\mathcal{G}\times\mathcal{M}$ from $(v_{0},W)$.
Now, thanks to Lemma 1, since Eve wins in $\mathcal{G}\times\mathcal{M}$, she
has a positional winning strategy. This induces a winning strategy in
$\mathcal{G}$ using $\mathcal{M}$ as memory structure, concluding the proof of
Lemma 2.

The game $\mathcal{G}\times\mathcal{M}$ defined above will be an important
tool in the proofs to follow. We will also rely on the following remark:
assume we want to prove that a strategy $\sigma$ is winning. Then it is enough
to show that for all plays $\pi$ consistent with $\sigma$, for all $k$,
$c(\pi_{k})^{-1}W\neq\emptyset$, where $\pi_{k}$ is the prefix of $\pi$ of
length $k$. This simple observation follows from the definition of safety
objectives.

### A Tighter Upper Bound

The memory structure $\mathcal{M}$ is not optimal. A first remark is that the
empty left quotient (which exists if $W\neq A^{\omega}$) can be removed from
the memory states as the game is lost. This is why by “left quotient” we mean
“non-empty left quotient of $W$”.

The second remark is the following: let $L_{1}$ and $L_{2}$ two left quotients
of $W$, such that $L_{1}\subseteq L_{2}$. With the same notations as above,
consider a vertex $v$ in the arena $\mathcal{A}$. If Eve wins from $(v,L_{1})$
in $\mathcal{G}\times\mathcal{M}$, then she also wins from $(v,L_{2})$:
indeed, she can play as she would have played from $(v,L_{1})$. Since this
ensures from $v$ that all plays are winning for $L_{1}$, then a fortiori they
are winning for $L_{2}$.

This suggests to restrict the memory states only to minimally winning left
quotients with respect to inclusion. Two issues arise:

  * •

which left quotients are winning depends on the current vertex, so the
semantics of a memory state can no longer be one left quotient, but rather a
left quotient for each possible vertex,

  * •

there may not exist minimally winning left quotients.

For the sake of presentation, we first show how to deal with the first issue,
assuming the second issue does not appear. Specifically, in the following
lemma, we assume that $\mathrm{Res}(W)$ is finite (i.e. $W$ is regular),
implying the existence of minimally winning left quotients. We will later drop
this assumption.

######  Lemma 3 (Upper bound in the regular case).

Assume that $\mathrm{Res}(W)$ is finite.

For all games $\mathcal{G}=(\mathcal{A},W)$, if Eve has a winning strategy
from an initial vertex $v_{0}$, then she has a winning strategy using at most
$K$ memory states, where $K$ is the width of $(\mathrm{Res}(W),\subseteq)$.

###### Proof.

We use the same notations as for the proof of Lemma 2, and construct a smaller
memory structure together with a winning strategy using this memory structure.
In this proof, by winning we mean winning in the game
$\mathcal{G}\times\mathcal{M}$.

Let $K$ be the cardinal of the maximal antichain of left quotients of $W$. We
construct a memory structure $\mathcal{M}^{*}=(\\{1,\ldots,K\\},1,\mu)$, and a
strategy $\sigma$ induced by the next-move function $\nu$.

Let $v$ be a vertex in $\mathcal{A}$. We consider the set of minimal left
quotients $L$ such that $(v,L)$ is winning. (Here we use the finiteness of
$\mathrm{Res}(W)$ to guarantee the existence of such left quotients.) This is
an antichain, so there are at most $K$ of them, we denote them by
$L_{1}(v),\ldots,L_{p}(v)$, for some $p\leq K$. The key property is that for
every left quotient $L$ such that $(v,L)$ is winning, there exists $i$ such
that $L_{i}(v)\subseteq L$. Furthermore, we choose $L_{1}(v_{0})$ such that
$L_{1}(v_{0})\subseteq W$. (Indeed, by assumption $(v_{0},W)$ is winning.)

We define the update function: $\mu(i,(v,v^{\prime}))$ is a $j$ such that
$L_{j}(v^{\prime})\subseteq L_{i}(v)\cdot c(v,v^{\prime})$. Note that in
general, such a $j$ may not exist; it does exist if $(v^{\prime},L_{i}(v)\cdot
c(v,v^{\prime}))$ is winning, and we will prove that this will always be the
case when playing the strategy $\sigma$.

We define the next-move function $\nu$ (inducing $\sigma$). Let $v\in
V_{\exists}$, and consider $(v,L_{i}(v))$: since Eve wins from there, there
exists an edge $(v,v^{\prime})\in E$ such that $(v^{\prime},L_{i}(v)\cdot
c(v,v^{\prime}))$ is winning. Define $\nu(v,i)$ to be this $v^{\prime}$.

We show that the strategy $\sigma$ is winning. Consider a play
$\pi=(v_{0},v_{1})\cdot(v_{1},v_{2})\cdots$ consistent with $\sigma$, and
$i_{0}\cdot i_{1}\cdots$ the sequence of memory states assumed along this
play. Denote $\pi_{k}$ the prefix of $\pi$ of length $k$, we prove that for
all $k$, $L_{i_{k}}(v_{k})\subseteq c(\pi_{k})^{-1}W$. Note that by
definition, $(v_{k},L_{i_{k}}(v_{k}))$ is winning, so
$L_{i_{k}}(v_{k})\neq\emptyset$, implying that
$c(\pi_{k})^{-1}W\neq\emptyset$.

We proceed by induction. For $k=0$, it follows from $L_{1}(v_{0})\subseteq W$.
Let $k>0$, the induction hypothesis is $L_{i_{k-1}}(v_{k-1})\subseteq
c(\pi_{k-1})^{-1}W$. We distinguish two cases.

  * •

Either $v_{k-1}$ belongs to Eve, then by construction of $\sigma$ we have that
$(v_{k},L_{i_{k-1}}(v_{k-1})\cdot c(v_{k-1},v_{k}))$ is winning. It follows
that the update function is well defined, and $L_{i_{k}}(v_{k})\subseteq
L_{i_{k-1}}(v_{k-1})\cdot c(v_{k-1},v_{k})$, which together with the induction
hypothesis implies $L_{i_{k}}(v_{k})\subseteq c(\pi_{k})^{-1}W$.

  * •

Or $v_{k-1}$ belongs to Adam. Since Adam cannot escape
$\mathcal{W}_{E}(\mathcal{G}\times\mathcal{M})$, we have that
$(v_{k},L_{i_{k-1}}(v_{k-1})\cdot c(v_{k-1},v_{k}))$ is winning, and the same
reasoning concludes.

It follows that the strategy $\sigma$ is winning, concluding the proof of
Lemma 3.

We now get rid of the regularity assumption. This means that for a vertex $v$,
there may not be a minimal left quotient $L$ such that $(v,L)$ is winning. We
present two ways to get around this difficulty: either an assumption on $W$,
or an assumption on the games.

######  Lemma 4 (Upper bound – well founded assumption).

Assume that $(\mathrm{Res}(W),\subseteq)$ is well-founded.

For all games $\mathcal{G}=(\mathcal{A},W)$, if Eve has a winning strategy
from an initial vertex $v_{0}$, then she has a winning strategy using at most
$K$ memory states, where $K$ is the width of $(\mathrm{Res}(W),\subseteq)$.

Consequently, $\mathrm{mem}(W)$ is smaller than or equal to the width of
$(\mathrm{Res}(W),\subseteq)$.

Note that if $W$ is regular, then $(\mathrm{Res}(W),\subseteq)$ is finite,
hence well-founded.

The proof of this lemma is the same as for Lemma 3, once we note that the well
founded assumption implies that for any vertex $v$, there exists a minimal
left quotient $L$ such that $(v,L)$ is winning.

######  Lemma 5 (Upper bound – finite degree assumption).

For all games $\mathcal{G}=(\mathcal{A},W)$ with finite degree, if Eve has a
winning strategy from an initial vertex $v_{0}$, then she has a winning
strategy using at most $K$ memory states, where $K$ is the width of
$(\mathrm{Res}(W),\subseteq)$.

Consequently, $\mathrm{mem}_{\textrm{fin-deg}}(W)$ is smaller than or equal to
the width of $(\mathrm{Res}(W),\subseteq)$.

###### Proof.

We use the same notations as for the proof of Lemma 3, and construct a memory
structure together with a winning strategy using this memory structure.

Let $K$ be the cardinal of the maximal antichain of left quotients of $W$. We
construct the memory structure $\mathcal{M}^{*}=(\\{1,\ldots,K\\},1,\mu)$, and
the strategy $\sigma$ induced by the next-move function $\nu$.

Let $v$ be a vertex in $\mathcal{A}$. We consider the set $\mathcal{W}(v)$ of
left quotients $L$ such that $(v,L)$ is winning. We split $\mathcal{W}(v)$
into maximal decreasing (finite or infinite) sequences of left quotients,
denoted $\ell_{1}(v),\ldots,\ell_{p}(v)$, for some $p\leq K$. Furthermore, we
choose $\ell_{1}(v_{0})$ such that $W\in\ell_{1}(v_{0})$. (Indeed, by
assumption $(v_{0},W)$ is winning.)

We say that $(v,\ell)$ is winning if for all $L\in\ell$, we have that $(v,L)$
is winning. For $\ell$ a sequence of left quotients and $a\in A$, we define
$\ell\cdot a$ component-wise. Note that even if $\ell$ is infinite, it may be
that $\ell\cdot a$ is finite.

We define the update function: $\mu(i,(v,v^{\prime}))$ is a $j$ as follows.

  * •

If $\ell_{i}(v)\cdot c(v,v^{\prime})$ is finite, denote $L\cdot
c(v,v^{\prime})$ its last element. Choose $j$ such that $L\cdot
c(v,v^{\prime})\in\ell_{j}(v^{\prime})$. Note that in general, such a $j$ may
not exist; it does exist if $(v^{\prime},\ell_{i}(v)\cdot c(v,v^{\prime}))$ is
winning, and we will prove that this will always be the case when playing the
strategy $\sigma$.

  * •

If $\ell_{i}(v)\cdot c(v,v^{\prime})$ is infinite, then choose $j$ such that
$\ell_{j}(v^{\prime})$ has an infinite intersection with $\ell_{i}(v)\cdot
c(v,v^{\prime})$. Such a $j$ exists without any assumption.

We define the next-move function $\nu$ (inducing $\sigma$). Let $v\in
V_{\exists}$, and consider $(v,\ell_{i}(v))$. Let $L\in\ell_{i}(v)$, Eve wins
from $(v,L)$, so there exists an edge $(v,v^{\prime})\in E$ such that
$(v^{\prime},L\cdot c(v,v^{\prime}))$ is winning, we say that
$(v,v^{\prime})\in E$ is good for $L$. Since $\mathcal{W}(v^{\prime})$ is
upward closed, if $(v,v^{\prime})\in E$ is good for $L$, then it is good for
every $L^{\prime}$ such that $L\subseteq L^{\prime}$. We argue that there
exists an edge $(v,v^{\prime})\in E$ that is good for all $L\in\ell_{i}(v)$,
i.e. such that $(v^{\prime},\ell_{i}(v)\cdot c(v,v^{\prime}))$ is winning;
define $\nu(v,i)$ to be this $v^{\prime}$. There are two cases:

  * •

Either $\ell_{i}(v)$ is finite, denote $L$ its last element. Since
$\ell_{i}(v)$ is decreasing, an edge good for $L$ is good for all
$L^{\prime}\in\ell_{i}(v)$.

  * •

Or $\ell_{i}(v)$ is infinite. The vertex $v$ has finite degree, so there
exists an edge which is good for infinitely many $L\in\ell_{i}(v)$. Since
$\ell_{i}(v)$ is decreasing, it is good for all $L^{\prime}\in\ell_{i}(v)$.

We show that the strategy $\sigma$ is winning. Consider a play
$\pi=(v_{0},v_{1})\cdot(v_{1},v_{2})\cdots$ consistent with $\sigma$, and
$i_{0}\cdot i_{1}\cdots$ the sequence of memory states assumed along this
play. Denote $\pi_{k}$ the prefix of $\pi$ of length $k$, we prove that for
all $k$, there exists $L\in\ell_{i_{k}}(v_{k})$ such that $L\subseteq
c(\pi_{k})^{-1}W$. Note that by definition, $(v_{k},\ell_{i_{k}}(v_{k}))$ is
winning, so $c(\pi_{k})^{-1}W\neq\emptyset$.

We proceed by induction. For $k=0$, it follows from $W\in\ell_{1}(v_{0})$. Let
$k>0$, the induction hypothesis implies the existence of
$L\in\ell_{i_{k-1}}(v_{k-1})$ such that $L\subseteq c(\pi_{k-1})^{-1}W$. We
distinguish two cases, and denote $c_{k}=c(v_{k-1},v_{k})$.

  * •

Either $v_{k-1}$ belongs to Eve, then by construction of $\sigma$ we have that
$(v_{k},\ell_{i_{k-1}}(v_{k-1})\cdot c_{k})$ is winning. It follows that the
update function is well defined, and:

    1. (1)

If $\ell_{i_{k-1}}(v_{k-1})\cdot c_{k}$ is finite, denote $L^{\prime}\cdot
c_{k}$ its last element, we have $L^{\prime}\cdot
c_{k}\in\ell_{i_{k}}(v_{k})$. Since $L^{\prime}\cdot c_{k}$ is the last
element of $\ell_{i_{k-1}}(v_{k-1})\cdot c_{k}$, it follows that
$L^{\prime}\subseteq L$. We have thus $L^{\prime}\cdot c_{k}\subseteq L\cdot
c_{k}$, so $L^{\prime}\subseteq c(\pi_{k})^{-1}W$, and $L^{\prime}\cdot
c_{k}\in\ell_{i_{k}}(v_{k})$.

    2. (2)

If $\ell_{i_{k-1}}(v_{k-1})\cdot c_{k}$ is infinite, $\ell_{i_{k}}(v_{k})$ has
an infinite intersection with $\ell_{i_{k-1}}(v_{k-1})\cdot c_{k}$. So there
exists $L^{\prime}\subseteq L$ with $L^{\prime}\in\ell_{i_{k-1}}(v_{k-1})$
such that $L^{\prime}\cdot c_{k}$ is in this intersection. We have
$L^{\prime}\cdot c_{k}\in\ell_{i_{k}}(v_{k})$ and $L^{\prime}\subseteq
c(\pi_{k})^{-1}W$.

  * •

Or $v_{k-1}$ belongs to Adam. Since Adam cannot escape
$\mathcal{W}_{E}(\mathcal{G}\times\mathcal{M})$, we have that
$(v_{k},\ell_{i_{k-1}}(v_{k-1})\cdot c_{k})$ is winning, and the same
reasoning concludes.

It follows that the strategy $\sigma$ is winning, concluding the proof of
Lemma 5.

### A Matching Lower Bound

######  Lemma 6 (Lower bound).

There exists a game $\mathcal{G}=(\mathcal{A},W)$ with finite degree and an
initial vertex $v_{0}$ where Eve has a winning strategy, but no winning
strategy using less than $K$ memory states, where $K$ is the width of
$(\mathrm{Res}(W),\subseteq)$.

Consequently, $\mathrm{mem}_{\textrm{fin-deg}}(W)$ and $\mathrm{mem}(W)$ are
both greater than or equal to the width of $(\mathrm{Res}(W),\subseteq)$.

###### Proof.

Consider $\\{w_{1}^{-1}W,\ldots,w_{K}^{-1}W\\}$ an antichain of left quotients
of $W$. For $i\neq j$, there exists $u_{i,j}\in A^{\omega}$ such that
$u_{i,j}\in w_{i}^{-1}W$ and $u_{i,j}\notin w_{j}^{-1}W$.

We describe the game, illustrated in Figure 1. A play consists in three steps:

  1. (1)

From $v_{0}$ to $v^{\prime}_{0}$: Adam chooses a word in
$\\{w_{1},\ldots,w_{K}\\}$;

  2. (2)

Eve chooses between $K$ options;

  3. (3)

say Eve chose the $i$th option, then Adam chooses between the $K-1$ words
$u_{i,j}$ for $j\neq i$.

We first show that Eve has a winning strategy from $v_{0}$, using $K$ memory
states. It consists in choosing the $i$th option whenever Adam chooses the
word $u_{i}$: whatever Adam chooses at the third step, $w_{i}\cdot u_{i,j}\in
W$.

We now show that there exists no winning strategy using less than $K$ memory
states. Indeed, such a strategy will not comply with the above strategy and
for some $i\neq j$, choose the $j$th option if Adam chooses $w_{i}$. Then Adam
wins by playing $u_{i,j}$, since $w_{i}\cdot u_{i,j}\notin W$.

$v_{0}$$\vdots$$v^{\prime}_{0}$$v_{1}$$\cdots$$v_{i}$$v_{K}$$\cdots$$\vdots$$w_{1}$$w_{2}$$w_{K-1}$$w_{K}$$u_{i,1}$$u_{i,2}$$u_{i,K-1}$$u_{i,K}$
Figure 1. The lower bound.

Theorem 1 easily follows from combining the upper bound and lower bound
lemmas.

##  5\. Examples and Applications

In this section, we instantiate Theorem 1 on different examples. We chose four
examples:

  * •

The outbidding objective shows the difference between graphs with finite
degree and graphs with infinite degree; in particular, it gives a counter
example to Lemma 5 when dropping the finite degree assumption,

  * •

The energy objective is a non-regular half-positional safety objective,

  * •

The generalized safety objective is a regular safety objective for which the
partially ordered set of left quotients has a nice well-known combinatorial
structure,

  * •

The boundedness objective is a central piece in the theory of regular cost
functions.

When representing the partial order $(\mathrm{Res}(W),\subseteq)$ for a given
$W$, we use the following convention: a black edge from $L$ to $L^{\prime}$
means that $L\subseteq L^{\prime}$, and a red edge labeled $a$ from $L$ to
$L^{\prime}$ means that $L^{\prime}=L\cdot a$, so the red structure is the
minimal (although possibly infinite) deterministic automaton recognizing $W$.

### Outbidding Games

Let $A=\\{a,b,c\\}$ and $W=\\{a^{n}\cdot b^{p}\cdot c^{\omega}\mid n\leq
p\\}\cup\\{a^{\omega}\\}\cup a^{*}\cdot b^{\omega}$. It is a non-regular
safety objective, called the outbidding objective. The figure 2 represents the
partial order $(\mathrm{Res}(W),\subseteq)$. Its width is three: there are two
incomparable infinite increasing sequences of left quotients,
$((a^{n})^{-1}W)_{n\in\mathbb{N}}$ and $((b\cdot
a^{n})^{-1}W)_{n\in\mathbb{N}}$, and $c^{-1}W$.

$\varepsilon$$a$$a^{2}$$a^{3}$$a^{4}$$a^{5}$$\ldots$$b$$ab$$a^{2}b$$a^{3}b$$a^{4}b$$a^{5}b$$\ldots$$c$$a$$a$$a$$a$$a$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$b$$c$$b$$c$
Figure 2. The outbidding objective: more $b$’s than $a$’s.

Hence thanks to Theorem 1, $\mathrm{mem}_{\textrm{fin-deg}}(W)=3$. However,
there exists an outbidding game where Eve needs but needs infinite memory.
This does not contradict Theorem 1, as this game, represented in Figure 3, has
a vertex of infinite degree. It goes as follows: first Adam picks a number
$n$, and then Eve takes over: she has to pick a number $p$, higher than or
equal to $n$. A finite memory strategy can only choose from finitely many
options, hence cannot win against all strategies of Adam.

$v_{0}$$v^{\prime}_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{n}$$\vdots$$\vdots$$a$$a$$b$$b^{2}$$b^{3}$$b^{n}$$c$$c$$c$$c$
Figure 3. An outbidding game with infinite degree where Eve needs infinite
memory to win.

### Energy Games

The setup for the energy objective is the following: assume we are monitoring
a resource. We denote by $A$ the set of actions on this resource, which is any
monotonic function $f:\mathbb{N}\to\mathbb{N}$, as for instance:

  * •

consuming one unit of the resource,

  * •

reloading by one unit,

  * •

emptying the resource,

  * •

consuming half of the current energy level.

Define the energy objective by

$W=\\{w=w_{0}w_{1}\cdots\mid\textrm{ the energy level remains always non-
negative}\\}\ .$

It is a non-regular safety objective. Energy games and several variants have
been extensively studied [BFL+08, CD12, CdAHS03]. The Figure 4 represents the
partial order $(\mathrm{Res}(W),\subseteq)$, with only two actions: $a$
reloads by one unit, and $b$ consumes one unit. In general, if the actions are
monotonic, then the left quotients are totally ordered by inclusion, so thanks
to Theorem 1 we have $\mathrm{mem}_{\textrm{fin-deg}}(W)=1$.

$\varepsilon$$a$$a^{2}$$a^{3}$$a^{4}$$a^{5}$$\ldots$$a$$a$$a$$a$$a$$b$$b$$b$$b$$b$
Figure 4. The energy objective: always more $a$’s than $b$’s.

######  Corollary 2.

The energy games are half-positional.

### Generalized Safety Games

This example originates from the study of generalized reachability games
[FH10, FH13]. A generalized reachability objective is a (finite) conjunction
of reachability objectives. Here we take the opponent’s vantage point: a
generalized safety objective is a (finite) disjunction of (internal) safety
objectives. Specifically, let $A=\\{\bot,1,\ldots,k\\}$: each letter is a
color, and $\bot$ is uncolored. Let $W=\\{w=w_{0}w_{1}\cdots\mid\exists
i\in\\{1,\ldots,k\\},\forall n,w_{n}\neq i\\}$, it is satisfied if at least
one color is not seen along the play. It is a safety objective. The figure 4
represents the partial order $(\mathrm{Res}(W),\subseteq)$ for $k=3$. The left
quotients are all the strict subsets of $\\{1,\ldots,k\\}$. The width of this
partial order is $\binom{k}{\lfloor k/2\rfloor}$, according to the well known
Sperner’s Lemma from combinatorics.

$\varepsilon$$\\{1\\}$$\\{2\\}$$\\{3\\}$$\\{1,2\\}$$\\{1,3\\}$$\\{2,3\\}$$1$$2$$3$$2$$1$$3$$1$$3$$2$$\bot$$\bot,1$$\bot,2$$\bot,3$$\bot,1,2$$\bot,1,3$$\bot,2,3$
Figure 5. The generalized safety objective.

######  Corollary 3.

For all generalized safety games with $k$ colors, if Adam has a winning
strategy, then he has a winning strategy with $\binom{k}{\lfloor k/2\rfloor}$
memory states.

Furthermore, for all $k$, there exists a generalized safety game with $k$
colors where Adam has a winning strategy using $\binom{k}{\lfloor k/2\rfloor}$
memory states, but none using less memory states.

### Games with Counters

This example originates from the theory of regular cost functions [Col13]. Let
$N\in\mathbb{N}$, and define the boundedness objective $W_{N}$ involving a
counter as follows:

$W_{N}=\\{w\mid\textrm{the counter value in }w\textrm{ remains bounded by
}N\\}\ .$

For the set of actions, we consider any monotonic action (even non-regular),
i.e. function $f:\mathbb{N}\to\mathbb{N}$ such that if $i\leq j$ then
$f(i)\leq f(j)$, as for instance:

  * •

leaving the counter value unchanged,

  * •

incrementing the counter value by one,

  * •

resetting the counter value to zero,

  * •

dividing the counter value by two, rounded down,

  * •

increasing the counter value to the next power of two.

The objective $W_{N}$ is a regular safety objective.

######  Corollary 4.

The boundedness games are half-positional.

##  6\. Related Works

The study of memory requirements in games has a long history.

Before 2014 – the publication of the conference version of this paper. The
first general result in this direction is about Muller objectives: in [DJW97],
the authors show how to compute the exact memory requirements by looking at
the so-called Zielonka tree [Zie98]. This is orthogonal to our results, as the
Muller objectives only specify the limit behaviour (what is seen infinitely
often), whereas we consider here only the behaviours in the finite. Gimbert
and Zielonka [GZ05] (see also [Gim07]) gave a characterization of all payoff
functions (extending objectives to a quantitative setting) for which both
players have memoryless optimal strategies.

Eryk Kopczyński investigated memory requirements for $\omega$-regular
objectives [Kop09], asking the following question: given a $\omega$-regular
objective, can we compute its memory requirement? This fascinating question
that we call the Kopczyński programme remains open to this day. One of the
many contributions of Kopczyński in this line of work was to introduce the
notion of chromatic memory: the memory structure only considers the sequence
of colours, and not the sequence of edges. Kopczyński constructed an algorithm
to compute the chromatic memory requirements of an $\omega$-regular objective,
and conjectured that this coincides with general memory requirements.

After 2014. Casares [Cas22] has disproved Kopczyński’s conjecture, and in
particular has shown that chromatic memory requirements are hard to compute:
for Muller objectives, deciding whether there is a memory structure of size
$k$ becomes NP-complete and equivalent to minimizing transition-based
deterministic Rabin automata. In this direction, Casares, Colcombet and
Lehtinen [CCL22] showed that computing general memory requirements for Muller
objectives is equivalent to minimizing good-for-games automata. A result by
Bouyer, Randour, and Vandenhove [BRV22] provides a link between the chromatic
memory requirements of all $\omega$-regular objectives (not only Muller
objectives) and their representation as transition-based deterministic parity
automata, but with less tight bounds on the minimal memory structures. Bouyer
et al. [BLO+22] extended the results of Gimbert and Zielonka [GZ05] to
chromatic finite memory.

A promising line of work extending the approach initiated in this paper uses
the notion of universal graphs, initially introduced for understanding
algorithms solving games [CFGO22], and later used by Ohlmann for giving a
characterisation of all positionally determined objectives [Ohl21, Ohl22].

The subsequent works most related to the present results are by Bouyer,
Casares, Randour and Vandenhove [BCRV22], and by Bouyer, Fijalkow, Randour,
and Vandenhove [BFRV22]. The first give a characterization of half-positional
objectives recognized by deterministic Büchi automata, and the second
characterizations of chromatic memory requirements for open and closed
objectives, as well as complexity-theoretic results about computing these
requirements. Both are technically rooted in the very ideas developed in this
paper.

Technically unrelated but close in spirit, the article [BLT22] establishes the
existence of finite-memory optimal strategies from topological properties of
objectives. There are major differences with our work: their framework is
different (they study _concurrent_ games that are not played _on graphs_), and
their aim is to establish the existence of finite-memory optimal strategies
for many objectives, but not to understand precisely the memory requirements
of some class of objectives.

## Conclusion and Perspectives

We considered general safety objectives and characterized their memory
requirements. Specifically, the memory requirements of a safety objective $W$
is the width of the partially ordered set $(\mathrm{Res}(W),\subseteq)$. This
is the first general result characterizing the memory requirements for some
non-regular objectives, based on their topological properties. Back in 2014,
we hoped that this would be a stepping stone for obtaining memory requirements
characterizations for other classes of objectives. As we have discussed in the
related works section this hope has materialised, with many results along this
line. We now only hope that there will be more: the long-term goal is indeed
to characterise memory requirements for all $\omega$-regular objectives, a
research programme started by Kopczyński around 2006 [Kop09] and far from
over.

## References

  * [BCRV22] Patricia Bouyer, Antonio Casares, Mickael Randour, and Pierre Vandenhove.  Half-positional objectives recognized by deterministic büchi automata.  In Bartek Klin, Slawomir Lasota, and Anca Muscholl, editors, CONCUR, volume 243 of LIPIcs, pages 20:1–20:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.CONCUR.2022.20.
  * [BFL+08] Patricia Bouyer, Ulrich Fahrenberg, Kim Guldstrand Larsen, Nicolas Markey, and Jirí Srba.  Infinite runs in weighted timed automata with energy constraints.  In Franck Cassez and Claude Jard, editors, FORMATS, volume 5215 of Lecture Notes in Computer Science, pages 33–47. Springer, 2008.
  * [BFRV22] Patricia Bouyer, Nathanaël Fijalkow, Mickael Randour, and Pierre Vandenhove.  How to play optimally for regular objectives?  CoRR, abs/2210.09703, 2022.  arXiv:2210.09703, doi:10.48550/arXiv.2210.09703.
  * [BLO+22] Patricia Bouyer, Stéphane Le Roux, Youssouf Oualhadj, Mickael Randour, and Pierre Vandenhove.  Games where you can play optimally with arena-independent finite memory.  Logical Methods in Computer Science, 18(1), 2022.  doi:10.46298/lmcs-18(1:11)2022.
  * [BLT22] Patricia Bouyer, Stéphane Le Roux, and Nathan Thomasset.  Finite-memory strategies in two-player infinite games.  In Florin Manea and Alex Simpson, editors, CSL, volume 216 of LIPIcs, pages 8:1–8:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.CSL.2022.8.
  * [BRV22] Patricia Bouyer, Mickael Randour, and Pierre Vandenhove.  Characterizing omega-regularity through finite-memory determinacy of games on infinite graphs.  In Petra Berenbrink and Benjamin Monmege, editors, STACS, volume 219 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1–16:16, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.STACS.2022.16.
  * [Cas22] Antonio Casares.  On the minimisation of transition-based Rabin automata and the chromatic memory requirements of Muller conditions.  In CSL, volume 216, pages 12:1–12:17, 2022.  doi:10.4230/LIPIcs.CSL.2022.12.
  * [CCL22] Antonio Casares, Thomas Colcombet, and Karoliina Lehtinen.  On the size of good-for-games Rabin automata and its link with the memory in Muller games.  In Mikołaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, ICALP, volume 229 of LIPIcs, pages 117:1–117:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.ICALP.2022.117.
  * [CD12] Krishnendu Chatterjee and Laurent Doyen.  Energy parity games.  Theoretical Computer Science, 458:49–60, 2012.
  * [CdAHS03] Arindam Chakrabarti, Luca de Alfaro, Thomas A. Henzinger, and Mariëlle Stoelinga.  Resource interfaces.  In Rajeev Alur and Insup Lee, editors, EMSOFT, volume 2855 of Lecture Notes in Computer Science, pages 117–133. Springer, 2003.
  * [CFGO22] Thomas Colcombet, Nathanaël Fijalkow, Pawel Gawrychowski, and Pierre Ohlmann.  The theory of universal graphs for infinite duration games.  Logical Methods in Computer Science, 18(3), 2022.  doi:10.46298/lmcs-18(3:29)2022.
  * [CFH14] Thomas Colcombet, Nathanaël Fijalkow, and Florian Horn.  Playing safe.  In Venkatesh Raman and S. P. Suresh, editors, FSTTCS, volume 29 of LIPIcs, pages 379–390. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014.  doi:10.4230/LIPIcs.FSTTCS.2014.379.
  * [Col13] Thomas Colcombet.  Regular cost functions, part I: Logic and algebra over words.  Logical Methods in Computer Science, 9(3), 2013.
  * [DJW97] Stefan Dziembowski, Marcin Jurdziński, and Igor Walukiewicz.  How much memory is needed to win infinite games?  In LICS, pages 99–110. IEEE Computer Society, 1997.
  * [FH10] Nathanaël Fijalkow and Florian Horn.  The surprizing complexity of reachability games.  CoRR, abs/1010.2420, 2010.
  * [FH13] Nathanaël Fijalkow and Florian Horn.  Les jeux d’accessibilité généralisée.  Technique et Science Informatiques, 32(9-10):931–949, 2013.
  * [Gim07] Hugo Gimbert.  Jeux Positionnels.  PhD thesis, Université Paris 7, 2007.
  * [GTW02] Erich Grädel, Wolfgang Thomas, and Thomas Wilke, editors.  Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 of Lecture Notes in Computer Science. Springer, 2002.
  * [GZ05] Hugo Gimbert and Wiesław Zielonka.  Games where you can play optimally without any memory.  In CONCUR 2005, pages 428–442, 2005.  doi:10.1007/11539452_33.
  * [Kop09] Eryk Kopczyński.  Half-Positional Determinacy of Infinite Games.  PhD thesis, University of Warsaw, 2009.
  * [Kup14] Orna Kupferman.  Variations on safety.  In Erika Ábrahám and Klaus Havelund, editors, TACAS, volume 8413 of Lecture Notes in Computer Science, pages 1–14. Springer, 2014.
  * [Ohl21] Pierre Ohlmann.  Monotonic graphs for parity and mean-payoff games.  PhD thesis, IRIF – Research Institute on the Foundations of Computer Science, 2021.
  * [Ohl22] Pierre Ohlmann.  Characterizing positionality in games of infinite duration over infinite graphs.  In Christel Baier and Dana Fisman, editors, LICS, pages 22:1–22:12. ACM, 2022.  doi:10.1145/3531130.3532418.
  * [Zie98] Wiesław Zielonka.  Infinite games on finitely coloured graphs with applications to automata on infinite trees.  Theoretical Computer Science, 200(1-2):135–183, 1998.