3 papers
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…
cs.LO2019
On the Monniaux Problem in Abstract Interpretation
Nathanaël Fijalkow, Engel Lefaucheux, Pierre Ohlmann +3
The Monniaux Problem in abstract interpretation asks, roughly speaking, whether the following question is decidable: given a program , a safety (\emph{e.g.}, non-reachability) s…
cs.GT2018
The complexity of mean payoff games using universal graphs
Nathanaël Fijalkow, Paweł Gawrychowski, Pierre Ohlmann
We study the computational complexity of solving mean payoff games. This class of games can be seen as an extension of parity games, and they have similar complexity status: in bot…