5 papers · 1 filter
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…
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…
First order synthesis for data words revisited
Julien Grange, Mathieu Lehaut
We carry on the study of the synthesis problem on data words for fragments of first order logic, and delineate precisely the border between decidability and undecidability.
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…
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…