89 citations · 131 across the 24 of their papers we have counts for
5 papers · 1 filter
Monadic dependence from reducts, and applications to twin-width of oriented graphs
Hector Buffière, Yuquan Lin, Patrice Ossona de Mendez
We study monadic dependence of binary relational structures including at least one antisymmetric relation. Our cornerstone result gives sufficient conditions for proving that a str…
Modulo-Counting First-Order Logic on Bounded Expansion Classes
J. Nesetril, P. Ossona de Mendez, S. Siebertz
We prove that, on bounded expansion classes, every first-order formula with modulo counting is equivalent, in a linear-time computable monadic expansion, to an existential first-or…
Twin-width and permutations
Édouard Bonnet, Jaroslav Nešetřil, Patrice Ossona de Mendez +2
Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomassé, and Watrigant introduced the twin-width of graphs, which is a parameter describi…
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…
Shrub-depth: Capturing Height of Dense Graphs
Robert Ganian, Petr Hliněný, Jaroslav Nešetřil +2
The recent increase of interest in the graph invariant called tree-depth and in its applications in algorithms and logic on graphs led to a natural question: is there an analogousl…