Satisfiability Solving and Model Generation for Quantified First-Order Logic Formulas

被引:0
作者
Gladisch, Christoph D. [1 ]
机构
[1] KIT, Inst Theoret Informat, Karlsruhe, Germany
来源
FORMAL VERIFICATION OF OBJECT-ORIENTED SOFTWARE | 2011年 / 6528卷
关键词
D O I
暂无
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
The generation of models, i.e. interpretations, that satisfy first-order logic (FOL) formulas is an important problem in different application domains, such as, e.g., formal software verification, testing, and artificial intelligence. Satisfiability modulo theory (SMT) solvers are the state-of-the-art techniques for handling this problem. A major bottleneck is, however, the handling of quantified formulas. Our contribution is a model generation technique for quantified formulas that is powered by a verification technique. The model generation technique can be used either stand-alone for model generation, or as a precomputation step for SMT solvers to eliminate quantifiers. Quantifier elimination in this sense is sound for showing satisfiability but not for refutational or validity proofs. A prototype of this technique is implemented.
引用
收藏
页码:76 / 91
页数:16
相关论文
共 26 条
  • [1] [Anonymous], ELECT NOTES THEOR CO
  • [2] [Anonymous], LNCS
  • [3] [Anonymous], LNCS LNAI
  • [4] [Anonymous], 2000, DYNAMIC LOGIC CAMBRI, DOI DOI 10.7551/MITPRESS/2516.001.0001
  • [5] [Anonymous], KARLSRUHE REPORTS IN
  • [6] [Anonymous], 2006, YICES SMT SOLVER
  • [7] [Anonymous], APPL LOGIC SERIES
  • [8] [Anonymous], THESIS U WROCLAW
  • [9] [Anonymous], LNCS
  • [10] [Anonymous], STTT