3 papers
cs.LO2026
Order-invariant cluster first-order logic on graph classes of bounded degree
Fatemeh Ghasemi, Julien Grange
We introduce a new logic, called \emph{cluster first-order logic}, a restricted fragment of first-order logic specifically designed to study order invariance. An order-invariant fo…
cs.DM2025
Weakly-sparse and strongly flip-flat classes of graphs are uniformly almost-wide
Fatemeh Ghasemi, Julien Grange, Mamadou Moustapha Kanté +1
In this work we take a step towards characterising strongly flip-flat classes of graphs. Strong flip-flatness appears to be the analogue of uniform almost-wideness in the setting o…
cs.LO2025
About the Expressive Power and Complexity of Order-Invariance with Two Variables
Bartosz Bednarczyk, Julien Grange
Order-invariant first-order logic is an extension of first-order logic FO where formulae can make use of a linear order on the structures, under the proviso that they are order-inv…