loading...
Quantified Constraints and Containment Problems
June 24-June 27
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2008.152008 23rd Annual IEEE Symposium on Lo ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
We study two containment problems related to the quantified constraint satisfaction problem (QCSP). Firstly, we give a combinatorial condition on finite structures A and B that is necessary and sufficient to render QCSP(A) a subset of QCSP(B). The required condition is the existence of a positive integer r such that there is a surjective homomorphism from the power structure A^r to B. We note??that this condition is already necessary to guarantee containment of the Pi_2 restriction of QCSP, that is Pi_2-CSP(A) a subset of Pi_2-CSP(B).??Since we are able to give an effective bound on such an r, we provide a decision procedure for the model containment problem with non-deterministic double-exponential time complexity. Secondly, we prove that the entailment problem for quantified conjunctive-positive first-order logic is decidable. That is, given two sentences phi and psi of first-order logic with no instances of negation or disjunction,??we give an algorithm that determines whether "phi implies psi" is true in all structures (models). Our result is in some sense tight, since we show that the entailment problem for positive first-order logic (i.e. quantified conjunctive-positive logic plus disjunction) is undecidable.
Citation:
Hubie Chen, Florent Madelaine, Barnaby Martin, "Quantified Constraints and Containment Problems," lics, pp.317-328, 2008 23rd Annual IEEE Symposium on Logic in Computer Science, 2008
Usage of this product signifies your acceptance of the Terms of Use.