Showing cs.LOShow all
2 papers · 1 filter
cs.LO2022
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…
cs.LO2020
A symmetric attractor-decomposition lifting algorithm for parity games
Marcin Jurdziński, Rémi Morvan, Pierre Ohlmann +1
Progress-measure lifting algorithms for solving parity games have the best worst-case asymptotic runtime, but are limited by their asymmetric nature, and known from the work of Cze…