research
∙
04/11/2023
The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)
We show that the big-O problem for max-plus automata is decidable and PS...
share
research
∙
03/19/2020
The Strahler number of a parity game
The Strahler number of a rooted tree is the largest height of a perfect ...
research
∙
07/27/2018
Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
Several distinct techniques have been proposed to design quasi-polynomia...
research
∙
07/23/2018
Undecidability of MSO+"ultimately periodic"
We prove that MSO on ω-words becomes undecidable if allowing to quantify...
research
∙
03/13/2018