The memory of ω \omega -regular and BC ⁡ ( 𝚺 2 0 ) {\color[rgb]{0.0195,0.2109,0.2539}\mathrm{BC}(\mathbf{\Sigma}^{0}_{2})} objectives

Antonio Casares, Pierre Ohlmann · 2025

Read The memory of ω \omega -regular and BC ⁡ ( 𝚺 2 0 ) {\color[rgb]{0.0195,0.2109,0.2539}\mathrm{BC}(\mathbf{\Sigma}^{0}_{2})} objectives by Antonio Casares, Pierre Ohlmann (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-05840.txt.

Introduction

Antonio Casares and Pierre Ohlmann settle how much memory a player needs to win endless games with complex goals. Their paper from twenty twenty-five works on two-player zero-sum games played on graphs, possibly endless ones. Memory is the count of states a winning plan must track. For omega-regular goals, even whether a given memory size could be decided was unknown.

The authors focus on goals in a class read by parity automata, possibly infinite ones. They build automata that capture all goals whose memory stays under a set cap. From this, memory over finite and infinite games turns out to match. It can be computed within NP bounds. A product rule bounds the memory of joined goals by the product of each part's memory. Chromatic memory, which updates only on seen colors, follows the same rules.

Catalog record

CREATORAntonio Casares, Pierre Ohlmann
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE127 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-05840

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The memory of ω \omega -regular and BC ⁡ ( 𝚺 2 0 ) {\color[rgb]{0.0195,0.2109,0.2539}\mathrm{BC}(\mathbf{\Sigma}^{0}_{2})} objectives Antonio Casares, Pierre Ohlmann Abstract In the context of 2-player zero-sum infinite duration games played on (potentially infinite) graphs, the memory of an objective is the smallest integer k k such that in any game won by Eve, she has a strategy with ≤ k \leq k states of memory. For ω \omega -regular objectives, checking whether the memory equals a given number k k was not known to be decidable. In this work, we focus on objectives in BC ⁡ ( 𝚺 2 0 ) {\color[rgb]{0.0195,0.2109,0.2539}\mathrm{BC}(\mathbf{\Sigma}^{0}_{2})} , i.e. recognised by a potentially infinite deterministic parity automaton. We provide a class of automata that recognise objectives with memory ≤ k \leq k , leading to the following results: • for ω \omega -regular objectives, the memory over finite and infinite games coincides and can be computed in NP ; • given two objectives W 1 W_{1} and W 2 W_{2} in BC ⁡ ( 𝚺 2 0 ) {\color[rgb]{0.0195,0.2109,0.2539}\mathrm{BC}(\mathbf{\Sigma}^{0}_{2})} and assuming W 1 W_{1} is prefix-independent, the memory of W 1 ∪ W 2 W_{1}\cup W_{2} is at most the product of the memories of W 1 W_{1} and W 2 W_{2} . Our results also apply to chromatic memory, the variant where strategies can update their memory state only depending on which colour is seen. University of Kaiserslautern-Landau, Germany and https://antonio-casares.github.io/ [email protected]://orcid.org/0000-0002-6539-2020Partially supported by Deutsche Forschungsgemeinschaft (grant number 522843867) and European Research Council (grant number 101089343). Part of this work was done while Casares was at the University of Warsaw, Poland, supported by the Polish National Science Centre (NCN) grant “Polynomial finite state computation” (2022/46/A/ST6/00072). CNRS, Laboratoire d’Informatique et des Systèmes (LIS), Marseille, France and https://pageperso.lis-lab.fr/pierre.ohlmann/ [email protected]://orcid.org/0000-0002-4685-5253 We thank Nathan Lhote for his participation in the scientific discussions which led to this paper. We also thank Pierre Vandenhove for pointing us to references concerning lifting results for memory. ccs Theory of computation Logic and verification keywords Infinite duration games, memory, omega-regular † † runningauthor: A. Casares and P. Ohlmann † † copyright: Antonio Casares and Pierre Ohlmann This document contains hyperlinks. Each occurrence of a notion is linked to its definition . On an electronic device, the reader can click on words or symbols (or just hover over them on some PDF readers) to see their definition. 1 Introduction Context: Strategy complexity in infinite duration games We study infinite duration games on graphs in which two players, called Eve and Adam, interact by moving a token along the edges of a (potentially infinite) edge-coloured directed graph. Each vertex belongs to one player, who chooses where to move next during a play. This interaction goes on for an infinite duration, producing an infinite path in the graph. The winner is determined according to a language of infinite sequences of colours W , called the objective of the game; Eve aims to produce a path coloured by a sequence in W , while Adam tries to prevent this. This model is widespread for its use in verification and synthesis [ 14 ] . In order to achieve their goal, players use strategies, which are representations of the course of all possible plays together with instructions on how to act in each scenario. In this work, we are interested in optimal strategies for Eve, that is, strategies that guarantee a victory whenever this is possible. More precisely, we are interested in the complexity of such strategies, or in other words, in the succinctness of the representation of the space of plays. Positionality. The simplest strategies are those that assign in advance an outgoing edge to each vertex owned by Eve, and always play along this edge, disregarding all the other features of the play. All the information required to implement such a strategy appears in the game graph itself. Objectives for which such strategies are sufficient to play optimally are called positional (or memoryless). Understanding positionality has been the object of a long line of research. The landmark results of Gimbert and Zielonka [ 21 ] and Colcombet and Niwiński [ 17 ] gave a good understanding of which objectives are bi-positional, i.e. positional for both players. More recently, Ohlmann proposed to use universal graphs as a tool for studying positionality (taking Eve’s point of view) [ 27 ] . This led to many advances in the study of positionality [ 2 , 25 ] , and most notably, a characterisation of positional \omega -regular objectives by Casares and Ohlmann [ 10 ] , together with a polynomial time decision procedure (and some other important corollaries, more discussion below). Strategies with memory. In many scenarios, playing optimally requires distinguishing plays that end in the same vertex. A seminal result of Büchi and Landweber [ 7 ] states that in finite games where the objective is an \omega -regular language, the winner has a winning strategy that can be implemented by a finite automaton processing the edges of the game; this result was later extended to infinite game graphs by Gurevich and Harrington [ 22 ] . Here, the states of the automaton are interpreted as memory states of the strategy, and a natural measure of the complexity of a strategy is the number of such states. More precisely, the memory of an objective W is the minimal k such that whenever Eve wins a game with objective W , she has a winning strategy with k states of memory. For \omega -regular objectives, this is always finite [ 7 , 22 ] , while the case of positionality discussed above corresponds to memory k=1 . Characterising the memory of objectives has been a recurrent research subject since the 1990s. Notable results include the characterisation for Muller objectives by Dziembowski, Jurdziński, and Walukiewicz [ 18 ] , or for closed objectives by Colcombet, Fijalkow and Horn [ 15 ] . However, these are all rather restricted classes of \omega -regular objectives. The problem of deciding the memory of \omega -regular objectives has been raised in many occasions (see for instance [ 23 , Sect. 9.2] , [ 4 , Sect. 4] , [ 16 , Conclusions] , or [ 3 ] ), but prior to this work, even computing the memory of open \omega -regular objectives was not known to be decidable. Chromatic memory. In the special case where the automata implementing strategies are only allowed to read the colours on the edges of the game graph, instead of the edges themselves, we speak of chromatic memory. In his PhD thesis, Kopczyński showed that, for prefix-independent \omega -regular objectives and over finite game graphs, the chromatic memory can be computed in exponential time [ 23 , Theorem 8.14] . Recently, it was shown that computing the chromatic memory of some restricted subclasses of \omega -regular objectives is in fact NP -complete: for Muller objectives [ 12 ] and for topologically open or closed objectives [ 3 ] . However, the chromatic and the unconstrained memory of objectives may differ, even exponentially [ 12 , 8 ] . Finite-to-infinite lift. In general, the memory of an objective may differ if we consider only finite game graphs or arbitrary

Read the complete text