Containment, Equivalence and Coreness from CSP to QCSP and beyond

2012/04/26 by Florent Madelaine, Madelaine, Florent, Barnaby Martin +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #cs.AI #cs.LO

paper · pdf · doi:10.48550/arxiv.1204.5981

arxiv created 2012/04/26 · openalex publication_date 2012/04/26 · arxiv updated 2012/04/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The constraint satisfaction problem (CSP) and its quantified extensions, whether without (QCSP) or with disjunction (QCSP_or), correspond naturally to the model checking problem for three increasingly stronger fragments of positive first-order logic. Their complexity is often studied when parameterised by a fixed model, the so-called template. It is a natural question to ask when two templates are equivalent, or more generally when one "contain" another, in the sense that a satisfied instance of the first will be necessarily satisfied in the second. One can also ask for a smallest possible equivalent template: this is known as the core for CSP. We recall and extend previous results on containment, equivalence and "coreness" for QCSP_or before initiating a preliminary study of cores for QCSP which we characterise for certain structures and which turns out to be more elusive.

Citations

• The core of a graph

Cited by

• From complexity to algebra and back: digraph classes, collapsibility and the PGP

Related

• Low-level dichotomy for Quantified Constraint Satisfaction Problems
• On the complexity of the model checking problem
• Fixed-Template Promise Model Checking Problems
• Model Checking Positive Equality-free FO: Boolean Structures and Digraphs of Size Three
• The complexity of positive first-order logic without equality II: The four-element case