4 papers
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…
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…