首页    期刊浏览 2024年09月19日 星期四
登录注册

文章基本信息

  • 标题:On Propositional QBF Expansions and Q-Resolution
  • 本地全文:下载
  • 作者:Mikolas Janota ; Joao Marques-Silva
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2013
  • 卷号:2013
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Over the years, proof systems for propositional satisfiability (SAT)have been extensively studied. Recently, proof systems forquantified Boolean formulas (QBFs) have also been gaining attention.Q-resolution is a calculus enabling producing proofs fromDPLL-based QBF solvers. While DPLL has become a dominating techniquefor SAT, QBF has been tackled by other complementary and competitiveapproaches. One of these approaches is based on expanding variablesuntil the formula contains only one type of quantifier; upon which aSAT solver is invoked. This approach motivates the theoreticalanalysis carried out in this paper. We focus on a two phase proof system,which expands the formula in the first phase and applies propositionalresolution in the second. Fragments of this proof system are defined andcompared to Q-resolution.

  • 关键词:Q-Resolution; quantified Boolean formulas; SAT
国家哲学社会科学文献中心版权所有