20 citations · 34 across the 12 of their papers we have counts for
13 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…
On guarded extensions of MMSNP
Alexey Barsukov, Florent R. Madelaine
Feder and Vardi showed that the class Monotone Monadic SNP without inequality (MMSNP) has a P vs NP-complete dichotomy if and only if such a dichotomy holds for finite-domain Const…
The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation
Catarina Carvalho, Florent Madelaine, Barnaby Martin +1
Let A be an idempotent algebra on a finite domain. By mediating between results of Chen and Zhuk, we argue that if A satisfies the polynomially generated powers property (PGP) and…
A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
Manuel Bodirsky, Florent Madelaine, Antoine Mottet
The logic MMSNP is a restricted fragment of existential second-order logic which allows to express many interesting queries in graph theory and finite model theory. The logic was i…
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…
Quantified Constraints and Containment Problems
Barnaby D. Martin, Hubie Chen, Florent R. Madelaine
The quantified constraint satisfaction problem is the problem to decide whether a positive Horn sentence, involving nothing more than the two quantifie…
QCSP on partially reflexive cycles - the wavy line of tractability
Florent Madelaine, Barnaby Martin
We study the (non-uniform) quantified constraint satisfaction problem QCSP(H) as H ranges over partially reflexive cycles. We obtain a complexity-theoretic dichotomy: QCSP(H) is ei…
On the complexity of the model checking problem
Florent Madelaine, Barnaby Martin
The model checking problem for various fragments of first-order logic has attracted much attention over the last two decades: in particular, for the primitive positive and the posi…
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…
Constraint Satisfaction with Counting Quantifiers
Florent Madelaine, Barnaby Martin, Juraj Stacho
We initiate the study of constraint satisfaction problems (CSPs) in the presence of counting quantifiers, which may be seen as variants of CSPs in the mould of quantified CSPs (QCS…
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…
Universal Structures and the logic of Forbidden Patterns
Florent R. Madelaine
Forbidden Patterns Problems (FPPs) are a proper generalisation of Constraint Satisfaction Problems (CSPs). However, we show that when the input is connected and belongs to a class…