10 citations · 15 across the 8 of their papers we have counts for
7 papers · 1 filter
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…
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…
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…
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…
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…