Equivalence Models for Quantified Boolean Formulas
By Hans Kleine Buening, Xishun Zhao
In this paper, the notion of equivalence models for quantified Boolean formulas with free variables is introduced. The computational complexity of the equivalence model checking problem in general case and some restricted cases are investigated. We also establish a connection between the structure of some quantified Boolean formulas and the structure of models.