Containment, Equivalence and Coreness from CSP to QCSP and beyond

Details Containment, Equivalence and Coreness from CSP to QCSP and beyond Containment, Equivalence and Coreness from CSP to QCSP and beyond

2012-04-26

arxiv.org/abs/1204.5981v1

Computer Science

Logic in Computer Science

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Containment, Equivalence and Coreness from CSP to QCSP and beyond does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Containment, Equivalence and Coreness from CSP to QCSP and beyond, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Containment, Equivalence and Coreness from CSP to QCSP and beyond will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-314871