具有自定义理论的 SMT 求解器？
SMT solver with custom theories?
我正在考虑做一些验证工作，我将常规树语法作为基础理论。
Z3 允许您使用未解释的函数定义您自己的东西，但是只要您的决策过程是递归的，这往往不会很好地工作。他们曾经允许使用插件，但我认为这已经被取消了。
我想知道，有没有人推荐一个不错的 SMT 求解器，让您可以为自定义理论编写决策程序？
考虑到大多数合理的 SMT 求解器都是开源的，因此有多种选择，您可以根据需要花费多少时间和精力来集成任何细节的理论求解器。
- OpenSMT http://verify.inf.usi.ch/opensmt 专为实现可插拔理论集成而构建。
- VeriT、Yices 和 CVC4 是开源的，您可以研究这些求解器中的理论集成。
- Z3 是开源的，可供您和其他人在其上构建。有一个用于 DPLL(T) 插件模式的 API，但我们在 Z3 的源代码开放时删除了它，同时也由于一个基本的限制：它不能很好地支持模型构建。用于插入理论的内部 APIs 原则上与外部 APIs 同构。 https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/nbjorner-aplas11.pdf. I would say a first prototype is much easier achieved using an outer loop around the solver. You get a propositional model from the solver and then check if it satisfies your background theory. You can also try the internal APIs. For some theories, this is fairly easy. See for example UTVPI https://github.com/Z3Prover/z3/blob/master/src/smt/theory_utvpi_def.h as a sample. For the theory of strings, it is fairly involved (because the theory requires substantial special case reasoning). The module z3str3 was integrated earlier this year https://github.com/Z3Prover/z3/blob/master/src/smt/theory_str.cpp, and development is still ongoing. It is about 10KLOC. Bui Phi Dep uses the older version of Z3 for an external theory integration https://github.com/diepbp/FAT 描述了整合理论的各种方法的较旧论文。这也是大量的代码，因为弦和换能器理论需要相当多的设置。对于愿意响应用户错误报告和请求的贡献者，我们 (Z3) 非常欢迎向 Z3 的主要分支提供未涵盖的理论和算法的额外贡献。字符串和树 acceptor/transducer space 中有相当多的回旋余地。
同样，我要说的是，对于第一个版本，您应该在外部集成方面走得更远，您可以让 SMT 求解器处理命题 SAT 和未解释的函数（如果需要，还可以处理算术）。然后，您可以向求解器询问模型并添加理论公理，直到您从求解器返回的命题模型与您的理论一致（或者您得到 UNSAT）。
并非命题模型中的所有任务都是相关的。您可以通过应用对偶传播 (http://www.cs.utexas.edu/users/hunt/FMCAD/FMCAD14/proceedings/29_niemetz.pdf).
来最小化您考虑的分配数量
我正在考虑做一些验证工作，我将常规树语法作为基础理论。
Z3 允许您使用未解释的函数定义您自己的东西，但是只要您的决策过程是递归的，这往往不会很好地工作。他们曾经允许使用插件，但我认为这已经被取消了。
我想知道，有没有人推荐一个不错的 SMT 求解器，让您可以为自定义理论编写决策程序？
考虑到大多数合理的 SMT 求解器都是开源的，因此有多种选择，您可以根据需要花费多少时间和精力来集成任何细节的理论求解器。
- OpenSMT http://verify.inf.usi.ch/opensmt 专为实现可插拔理论集成而构建。
- VeriT、Yices 和 CVC4 是开源的，您可以研究这些求解器中的理论集成。
- Z3 是开源的，可供您和其他人在其上构建。有一个用于 DPLL(T) 插件模式的 API，但我们在 Z3 的源代码开放时删除了它，同时也由于一个基本的限制：它不能很好地支持模型构建。用于插入理论的内部 APIs 原则上与外部 APIs 同构。 https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/nbjorner-aplas11.pdf. I would say a first prototype is much easier achieved using an outer loop around the solver. You get a propositional model from the solver and then check if it satisfies your background theory. You can also try the internal APIs. For some theories, this is fairly easy. See for example UTVPI https://github.com/Z3Prover/z3/blob/master/src/smt/theory_utvpi_def.h as a sample. For the theory of strings, it is fairly involved (because the theory requires substantial special case reasoning). The module z3str3 was integrated earlier this year https://github.com/Z3Prover/z3/blob/master/src/smt/theory_str.cpp, and development is still ongoing. It is about 10KLOC. Bui Phi Dep uses the older version of Z3 for an external theory integration https://github.com/diepbp/FAT 描述了整合理论的各种方法的较旧论文。这也是大量的代码，因为弦和换能器理论需要相当多的设置。对于愿意响应用户错误报告和请求的贡献者，我们 (Z3) 非常欢迎向 Z3 的主要分支提供未涵盖的理论和算法的额外贡献。字符串和树 acceptor/transducer space 中有相当多的回旋余地。
同样，我要说的是，对于第一个版本，您应该在外部集成方面走得更远，您可以让 SMT 求解器处理命题 SAT 和未解释的函数（如果需要，还可以处理算术）。然后，您可以向求解器询问模型并添加理论公理，直到您从求解器返回的命题模型与您的理论一致（或者您得到 UNSAT）。 并非命题模型中的所有任务都是相关的。您可以通过应用对偶传播 (http://www.cs.utexas.edu/users/hunt/FMCAD/FMCAD14/proceedings/29_niemetz.pdf).
来最小化您考虑的分配数量