5 citations · 8 across the 5 of their papers we have counts for
9 papers
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…
First-order separation over countable ordinals
Thomas Colcombet, Sam van Gool, Rémi Morvan
We show that the existence of a first-order formula separating two monadic second order formulas over countable ordinal words is decidable. This extends the work of Henckell and Al…
Learning automata and transducers: a categorical approach
Thomas Colcombet, Daniela Petrişan, Riccardo Stabile
In this paper, we present a categorical approach to learning automata over words, in the sense of the -algorithm of Angluin. This yields a new generic -like algorithm whi…
Unambiguous separators for tropical tree automata
Thomas Colcombet, Sylvain Lombardy
In this paper we show that given a max-plus automaton (over trees, and with real weights) computing a function and a min-plus automaton (similar) computing a function such…
On Reachability Problems for Low-Dimensional Matrix Semigroups
Thomas Colcombet, Joël Ouaknine, Pavel Semukhin +1
We consider the Membership and the Half-Space Reachability problems for matrices in dimensions two and three. Our first main result is that the Membership Problem is decidable for…
Parity games and universal graphs
Thomas Colcombet, Nathanaël Fijalkow
This paper is a contribution to the study of parity games and the recent constructions of three quasipolynomial time algorithms for solving them. We revisit a result of Czerwiński,…