4 citations · 6 across the 4 of their papers we have counts for
5 papers
Model-checking positive equality free logic on a fixed structure (direttissima)
Manuel Bodirsky, Marcin Kozik, Florent Madelaine +2
We give a new, direct proof of the tetrachotomy classification for the model-checking problem of positive equality-free logic parameterised by the model. The four complexity classe…
Complexity of conjunctive regular path query homomorphisms
Laurent Beaudou, Florent Foucaud, Florent R. Madelaine +2
A graph database is a digraph whose arcs are labeled with symbols from a fixed alphabet. A regular graph pattern (RGP) is a digraph whose edges are labeled with regular expressions…
From complexity to algebra and back: digraph classes, collapsibility and the PGP
Catarina Carvalho, Florent Madelaine, Barnaby Martin
Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idempotent polymorphisms of certain digraph classes. Our fir…
Containment, Equivalence and Coreness from CSP to QCSP and beyond
Florent Madelaine, Barnaby Martin
The constraint satisfaction problem (CSP) and its quantified extensions, whether without (QCSP) or with disjunction (QCSP_or), correspond naturally to the model checking problem fo…
The complexity of positive first-order logic without equality
Florent Madelaine, Barnaby Martin
We study the complexity of evaluating positive equality-free sentences of first-order (FO) logic over a fixed, finite structure B. This may be seen as a natural generalisation of t…