8 citations · 39 across the 15 of their papers we have counts for
5 papers · 1 filter
Linear rankwidth meets stability
Jaroslav Nesetril, Patrice Ossona de Mendez, Roman Rabinovich +1
Classes with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths. These results show a strong link between the…
Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
Jaroslav Nesetril, Patrice Ossona de Mendez, Roman Rabinovich +1
Classes with bounded rankwidth are MSO-transductions of trees and classes with bounded linear rankwidth are MSO-transductions of paths -- a result that shows a strong link between…
Model-Checking on Ordered Structures
Kord Eickmeyer, Jan van den Heuvel, Ken-ichi Kawarabayashi +6
We study the model-checking problem for first- and monadic second-order logic on finite relational structures. The problem of verifying whether a formula of these logics is true on…
Model-Checking for Successor-Invariant First-Order Formulas on Graph Classes of Bounded Expansion
Jan van den Heuvel, Stephan Kreutzer, Michał Pilipczuk +3
A successor-invariant first-order formula is a formula that has access to an auxiliary successor relation on a structure's universe, but the model relation is independent of the pa…
Down the Borel Hierarchy: Solving Muller Games via Safety Games
Daniel Neider, Roman Rabinovich, Martin Zimmermann
We transform a Muller game with n vertices into a safety game with (n!)^3 vertices whose solution allows to determine the winning regions of the Muller game and to compute a finite…