FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
Local Soundness for QBF Calculi

Authors: Martin Suda and Bernhard Gleiss

Paper Information

Title:Local Soundness for QBF Calculi
Authors:Martin Suda and Bernhard Gleiss
Proceedings:SAT Proceedings
Editors: Christoph M. Wintersteiger and Olaf Beyersdorff
Keywords:QBF calculi, IRM-calc, semantics, long-distance resolution, strategies, Curry-Howard correspondence
Abstract:

ABSTRACT. We develop new semantics for resolution-based calculi for Quantified Boolean Formulas, covering both the CDCL-derived calculi and the expansion-derived ones. The semantics is centred around the notion of a partial strategy for the universal player and allows us to show in a local, inference-by-inference manner that these calculi are sound. It also helps us understand some less intuitive concepts, such as the role of tautologies in long-distance resolution or the meaning of the ``star'' in the annotations of IRM. Furthermore, we show that a clause of any of these calculi can be, in the spirit of Curry-Howard correspondence, interpreted as a specification of the corresponding partial strategy. The strategy is total, i.e. winning, when specified by the empty clause.

Pages:18
Talk:Jul 10 15:00 (Session 55F: QBF I)
Paper: