20 citations · 34 across the 12 of their papers we have counts for
6 papers · 1 filter
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…
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…
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…
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…