4 papers
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…
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 …
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…