56 citations · 149 across the 22 of their papers we have counts for
4 papers · 1 filter
Playing Safe, Ten Years Later
Thomas Colcombet, Nathanaël Fijalkow, Florian Horn
We consider two-player games over graphs and give tight bounds on the memory size of strategies ensuring safety objectives. More specifically, we show that the minimal number of me…
Z-polyregular functions
Thomas Colcombet, Gaëtan Douéneau-Tabot, Aliaume Lopez
This paper introduces a robust class of functions from finite words to integers that we call Z-polyregular functions. We show that it admits natural characterizations in terms of l…
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…