7 papers
The memory of -regular and BC() objectives
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…
Infinite lexicographic products of positional objectives
Antonio Casares, Pierre Ohlmann, MichaÅ Skrzypczak +1
This paper contributes to the study of positional determinacy of infinite duration games played on potentially infinite graphs with neutral transitions. Recently, [Ohlmann, Theoret…
History-Deterministic Büchi Automata are Succinct
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 bee…
Games on Graphs: From Logic and Automata to Algorithms
Nathanaël Fijalkow, C. Aiswarya, Guy Avni +22
The objective of this book is to give a comprehensive presentation of the research field concerned with infinite duration games on graphs. Historically, these game models appeared…
Characterising memory in infinite games
Antonio Casares, Pierre Ohlmann
This paper is concerned with games of infinite duration played over potentially infinite graphs. Recently, Ohlmann (LICS 2022) presented a characterisation of objectives admitting…
Fast value iteration: A uniform approach to efficient algorithms for energy games
Michaël Cadilhac, Antonio Casares, Pierre Ohlmann
We study algorithms for solving parity, mean-payoff and energy games. We propose a systematic framework, which we call Fast value iteration, for describing, comparing, and proving…