Antonio Casares

Antonio Casares, Pierre Ohlmann

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 such that in any game won by Eve, she has a strategy with <= k states of memory. For omega-regular objectives, checking whether the memory equals a given number k was not known to be decidable. In this work, we focus on objectives in BC(Sigma0^2), i.e. recognised by a potentially infinite deterministic parity automaton. We provide a class of automata that recognise objectives with memory <= k, leading to the following results: (1) For omega-regular objectives, the memory over finite and infinite games coincides and can be computed in NP. (2) Given two objectives W1 and W2 in BC(Sigma0^2) and assuming W1 is prefix-independent, the memory of W1 U W2 is at most the product of the memories of W1 and W2. Our results also apply to chromatic memory, the variant where strategies can update their memory state only depending on which colour is seen.

Antonio Casares, Pierre Ohlmann, Michał Skrzypczak et al.

This paper contributes to the study of positional determinacy of infinite duration games played on potentially infinite graphs with neutral transitions. Recently, [Ohlmann, TheoretiCS 2023] established that positionality of prefix-independent objectives is preserved by finite lexicographic products. We propose two different notions of infinite lexicographic products indexed by arbitrary ordinals, and extend Ohlmann's result by proving that they also preserve positionality. In the context of one-player positionality, this extends positional determinacy results of [Grädel and Walukiewicz, Logical Methods in Computer Science 2006] to edge-labelled games and arbitrarily many priorities for both Max-Parity and Min-Parity. Moreover, we show that the Max-Parity objectives over countable ordinals are complete for the infinite levels of the difference hierarchy over $Σ^0_2$ and that Min-Parity is complete for the class $Σ^0_3$. We obtain therefore positional languages that are complete for all those levels, as well as new insights about closure under unions and neutral letters.

Antonio Casares, Keya Prakash, K. S. Thejaswini

We describe a history-deterministic Büchi automaton that has strictly less states than every language-equivalent deterministic Büchi automaton. This solves a problem that had been open since the introduction of history-determinism and actively investigated for over a decade. Our example automaton has 65 states, and proving its succinctness requires the combination of theoretical insights together with the aid of computers.

Antonio Casares, Olivier Idir, Denis Kuperberg et al.

We present a polynomial-time algorithm minimising the number of states of history-deterministic generalised coBüchi automata, building on the work of Abu Radi and Kupferman on coBüchi automata. On the other hand, we establish that the minimisation problem for both deterministic and history-deterministic generalised Büchi automata is NP-complete, as well as the problem of minimising at the same time the number of states and colours of history-deterministic generalised coBüchi automata.