56 citations · 149 across the 22 of their papers we have counts for
27 papers
An algebraic characterisation of Eve-positional languages
Thomas Colcombet, Olivier Idir
We present a new algebraic characterisation of Eve-positionality for -regular languages. It involves only a limited number of elementary local properties to be checked. An -r…
Expregular functions
Thomas Colcombet, Nathan Lhote, Pierre Ohlmann
Polyregular functions form a robust class of string-to-string functions with polynomial growth, as evidenced by Bojanczyk (2018). This class admits numerous descriptions and enjoys…
Regular expressions over countable words
Thomas Colcombet, A V Sreejith
We investigate the expressive power of regular expressions for languages of countable words and establish their expressive equivalence with logical and algebraic characterizations.…
Tree algebras and bisimulation-invariant MSO on finite graphs
Thomas Colcombet, Amina Doumane, Denis Kuperberg
We establish that the bisimulation invariant fragment of MSO over finite transition systems is expressively equivalent over finite transition systems to modal mu-calculus, a questi…
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…
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…
The Theory of Universal Graphs for Infinite Duration Games
Thomas Colcombet, Nathanaël Fijalkow, Paweł Gawrychowski +1
We introduce the notion of universal graphs as a tool for constructing algorithms solving games of infinite duration such as parity games and mean payoff games. In the first part w…
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…
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…
Cost Automata, Safe Schemes, and Downward Closures
David Barozzini, Lorenzo Clemente, Thomas Colcombet +1
In this work we prove decidability of the model-checking problem for safe recursion schemes against properties defined by alternating B-automata. We then exploit this result to sho…
Controlling a random population
Thomas Colcombet, Nathanaël Fijalkow, Pierre Ohlmann
Bertrand et al. introduced a model of parameterised systems, where each agent is represented by a finite state system, and studied the following control problem: for any number of…
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,…
Automata Minimization: a Functorial Approach
Thomas Colcombet, Daniela Petrişan
In this paper we regard languages and their acceptors - such as deterministic or weighted automata, transducers, or monoids - as functors from input categories that specify the typ…
Automata in the Category of Glued Vector Spaces
Thomas Colcombet, Daniela Petrişan
In this paper we adopt a category-theoretic approach to the conception of automata classes enjoying minimization by design. The main instantiation of our construction is a new clas…
Automata Minimization: a Functorial Approach
Thomas Colcombet, Daniela Petrişan
In this paper we regard languages and their acceptors -- such as deterministic or weighted automata, transducers, or monoids -- as functors from input categories that specify the t…
Boundedness in languages of infinite words
Mikołaj Bojańczyk, Thomas Colcombet
We define a new class of languages of -words, strictly extending -regular languages. One way to present this new class is by a type of regular expressions. The new expression…
Perfect Half Space Games
Thomas Colcombet, Marcin Jurdziński, Ranko Lazić +1
We introduce perfect half space games, in which the goal of Player 2 is to make the sums of encountered multi-dimensional weights diverge in a direction which is consistent with a…
An algebraic approach to MSO-definability on countable linear orderings
Olivier Carton, Thomas Colcombet, Gabriele Puppis
We develop an algebraic notion of recognizability for languages of words indexed by countable linear orderings. We prove that this notion is effectively equivalent to definability…
Logics with rigidly guarded data tests
Gabriele Puppis, Thomas Colcombet, Clemens Ley
The notion of orbit finite data monoid was recently introduced by Bojanczyk as an algebraic object for defining recognizable languages of data words. Following Buchi's approach, we…