5 papers
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…
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…
Specification and Automatic Verification of Computational Reductions
Julien Grange, Fabian Vehlken, Nils Vortmeier +1
We are interested in the following validation problem for computational reductions: for algorithmic problems and , is a given candidate reduction indeed a reduction fr…
Synthesis for prefix first-order logic on data words
Julien Grange, Mathieu Lehaut
We study the reactive synthesis problem for distributed systems with an unbounded number of participants interacting with an uncontrollable environment. Executions of those systems…
On the nonexistence of FO-continuous path and tree-decompositions
Julien Grange
Bojanczyk and Pilipczuk showed in their celebrated article "Definability equals recognizability for graphs of bounded treewidth" (LICS 2016) that monadic second-order logic can def…