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