SAT 2004 START ConferenceManager    


Looking Algebraically at Tractable Quantified Boolean Formulas

Hubie Chen and Victor Dalmau

Presented at The Seventh International Conference on Theory and Applications of Satisfiability Testing (SAT 2004), Vancouver, BC, Canada, 10-13 May 2004


Abstract

We make use of the algebraic theory that has been used to study the complexity of constraint satisfaction problems, to investigate tractable quantified boolean formulas. We give a new and simple algebraic proof of the tractability of quantified 2-satisfiability. We also give a purely algebraic characterization of models for quantified Horn formulas that were given by B\"{u}ning, Subramani, and Zhao, and described proof-theoretically.


  
START Conference Manager (V2.47.2)
Maintainer: rrgerber@softconf.com