10 citations · 18 across the 10 of their papers we have counts for
13 papers
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 been…
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…
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…
A positional -complete objective
Antonio Casares, Pierre Ohlmann, Pierre Vandenhove
We study zero-sum, turn-based games on graphs. In this note, we show the existence of a game objective that is -complete for the Borel hierarchy and that is positiona…
The Complexity of Simplifying -Automata through the Alternating Cycle Decomposition
Antonio Casares, Corto Mascle
In 2021, Casares, Colcombet and Fijalkow introduced the Alternating Cycle Decomposition (ACD), a structure used to define optimal transformations of Muller into parity automata and…
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…
From Muller to Parity and Rabin Automata: Optimal Transformations Preserving (History) Determinism
Antonio Casares, Thomas Colcombet, Nathanaël Fijalkow +1
We study transformations of automata and games using Muller conditions into equivalent ones using parity or Rabin conditions. We present two transformations, one that turns a deter…
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…
Half-Positional Objectives Recognized by Deterministic Büchi Automata
Patricia Bouyer, Antonio Casares, Mickael Randour +1
In two-player games on graphs, the simplest possible strategies are those that can be implemented without any memory. These are called positional strategies. In this paper, we char…
On the size of good-for-games Rabin automata and its link with the memory in Muller games
Antonio Casares, Thomas Colcombet, Karoliina Lehtinen
In this paper, we look at good-for-games Rabin automata that recognise a Muller language (a language that is entirely characterised by the set of letters that appear infinitely oft…
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…
On the Minimisation of Transition-Based Rabin Automata and the Chromatic Memory Requirements of Muller Conditions
Antonio Casares
In this paper, we relate the problem of determining the chromatic memory requirements of Muller conditions with the minimisation of transition-based Rabin automata. Our first contr…
Optimal Transformations of Muller Conditions
Antonio Casares, Thomas Colcombet, Nathanaël Fijalkow
In this paper, we are interested in automata over infinite words and infinite duration games, that we view as general transition systems. We study transformations of systems using…