Showing cs.LOShow all
2 papers · 1 filter
cs.LO2025
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.…
cs.LO2025
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…