能够删除特定约束的增量 SMT 求解器

2024-05-04

是否有增量 SMT 求解器或用于某些增量 SMT 求解器的 API,我可以在其中增量添加约束,在其中我可以通过某个标签/名称唯一地标识每个约束?

我想唯一地标识约束的原因是这样我可以稍后通过指定标签/名称来删除它们。 需要放弃约束是因为我之前的约束变得与时间无关。 我发现对于 Z3,我无法使用基于推送/弹出的增量方法,因为它遵循基于堆栈的想法,而我的要求是删除特定的早期/旧约束。 使用基于假设的 Z3 的其他增量方法,我必须执行格式为“(check-sat p1 p2 p3)”的 check-sat,即如果我有三个断言要检查,那么我将需要三个布尔常量 p1,p2 ,p3,但在我的实现中,我一次要检查数千个断言,间接需要数千个布尔常量。 我还检查了 JavaSMT(用于 SMT 求解器的 Java API),看看该 API 是否提供了一些更好的方法来处理此需求,但我只看到通过“addConstraint”或“push”添加约束的方法,并且无法找到任何方法删除或删除特定的约束,因为弹出是唯一可用的选项。

我想知道是否有增量解算器可以添加或删除由名称唯一标识的约束,或者是否有 API 可以提供替代方法来处理它。我将不胜感激任何建议或意见。


基于“堆栈”的方法在 SMTLib 中已经根深蒂固,因此我认为很难找到一个完全满足您需求的求解器。尽管我确实同意这将是一个很好的功能。

话虽如此,我可以想到两个解决方案。但两者都不能很好地满足您的特定用例,尽管它们都会work。归根结底,您希望能够在每次调用时挑选约束条件check-sat。不幸的是,这会很昂贵。每次求解器执行check-sat it learns许多基于所有当前断言的引理,以及许多内部数据结构都进行了相应的修改。基于堆栈的方法本质上允许求解器“回溯”到这些学习状态之一。但是,当然,这不允许像您观察到的那样进行挑选。

所以,我认为你只剩下以下之一:

使用 check-sat-假设

这基本上就是您已经描述的内容。但回顾一下,您只需给它们命名,而不是断言布尔值。所以这:

  (assert complicated_expression)

becomes

  ; for each constraint ci, do this:
  (declare-const ci Bool)
  (assert (= ci complicated_expression))
  ; then, check with whatever subset you want
  (check-sat-assuming (ci cj ck..))

这确实增加了您必须管理的布尔常量的数量,但从某种意义上说,这些都是您想要的“名称”。我知道您不喜欢这样,因为它引入了很多变量;事实确实如此。这是有充分理由的。请参阅此处的讨论:https://github.com/Z3Prover/z3/issues/1048 https://github.com/Z3Prover/z3/issues/1048

使用重置断言和:全局声明

这是一个变体,允许您在每次调用时任意挑选断言check-sat。但它会not便宜点。特别是,每次您按照此方法进行操作时,求解器都会忘记所学到的所有内容。但它会完全按照您的意愿行事。首要问题:

(set-option :global-declarations true)

并以某种方式在你的包装中自己跟踪所有这些。现在,如果您想任意“添加”约束,则无需执行任何操作。只需添加它即可。如果你想删除某些东西,那么你可以说:

 (reset-assertions)
 (assert your-tracked-assertion-1)
 (assert your-tracked-assertion-2)
;(assert your-tracked-assertion-3)  <-- Note the comment, we're skipping
 (assert your-tracked-assertion-4) 
 ..etc

等等。也就是说,你“删除”你不想要的那些。请注意,:global-declarations调用很重要,因为它将确保您调用时所有数据声明和其他绑定保持完整reset-assertions,它告诉求解器从其假设和学到的内容开始。

实际上,您正在管理自己的限制,正如您最初所希望的那样。

Summary

这些解决方案都不是您想要的,但它们都会起作用。如果不诉诸这两种解决方案之一,就没有符合 SMTLib 的方法可以完成您想要的操作。然而,个别求解器可能还有其他技巧。您可能需要咨询他们的开发人员,看看他们是否有针对此用例的定制内容。虽然我怀疑情况确实如此,但很高兴能找到答案!

另请参阅 Nikolaj 之前的回答,该回答非常相关:Z3 中的增量求解如何工作? https://stackoverflow.com/questions/16422018/how-incremental-solving-works-in-z3?rq=1

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

能够删除特定约束的增量 SMT 求解器 的相关文章

  • 如何让 z3 返回多个 unsat 核心、多个令人满意的作业

    我正在研究一个研究工具的一个组件 我有兴趣检索 对于 QF LRA 多个 最少或其他 UNSAT核心以及 多项 SAT 作业 我检查了论坛以获取有关此主题的早期讨论 例如 在逻辑 QF LRA 上使用 z3 时如何获得不同的 unsat 核
  • 使用函数在 z3 中创建列表

    我试图将这段伪代码转换为 SMT LIB 语言 但我卡住了 List function my fun int x list nil for i in 1 to x if some condition on i list concat i r
  • 【无标题】SMT贴片加工过程中需要注意的事项

    1 SMT贴片加工 技术员在产线上应佩戴好检验OK的防静电手环 金属片紧贴手腕并保持良好双手交替作业 插件前检查每个订单的电子元器件无错 混料 破损 变形 划伤等不良现象 2 电路板插件需要提前把电子物料准备好 注意电容极性方向须确认无误
  • (Z3Py) 函数声明有什么限制吗?

    函数声明有什么限制吗 例如 这段代码返回 unsat from z3 import def one op op arg1 arg2 if op 1 return arg1 arg2 if op 2 return arg1 arg2 if o
  • Z3 的参考资料 - 它是如何工作的[内部理论]?

    我有兴趣阅读 Z3 背后的内部理论 具体来说 我想了解 Z3 SMT 求解器的工作原理 以及它如何找到不正确模型的反例 我希望能够手动计算出一些非常简单的示例的跟踪 然而 所有 Z3 参考文献似乎都是如何在其中编码 或对其算法的非常高级的描
  • 有人尝试过用Z3本身来证明Z3吗?

    有没有人尝试证明Z3 http research microsoft com en us um redmond projects z3 与Z3本身 是否有可能使用 Z3 来证明 Z3 是正确的 更理论化的是 是否有可能使用 X 本身来证明工
  • Z3 将数组的默认值设置为零

    我正在尝试求解数组表达式的模型 其中数组的默认值等于 0 例如 我正在尝试解决这个例子 但我总是得到未知的结果 declare const arr Array Int Int declare const arr2 Array Int Int
  • 了解 z3 模型

    Z3Py 片段 x Int x fun Function fun IntSort IntSort IntSort phi ForAll x fun x x x print phi solve phi 永久链接 http rise4fun c
  • 如何估计在 z3 for SMT 中解决 SAT 部分所花费的时间?

    我已经使用探查器 gprof statshere http www ccs neu edu jaideep example2 stats包括调用图 并试图将所花费的时间分为两类 I SAT 求解部分 包括 纯 布尔传播和 纯 布尔冲突子句检
  • Z3 求解器中 MAxSMT 和用户定义成本函数的组合

    我正在使用 Z3 来优化带有一些软约束 带有加权 MaxSMT 的成本函数 我很好奇 MaxSMT 和用户定义的成本函数如何交互 求解器是否最小化 MaxSMT 成本和目标函数两者 是否有优先级机制 我找不到这方面的任何文档 如果我遗漏了什
  • Z3 实数算术和数据类型理论整合得不太好

    这与我之前问过的问题有关Z3 SMT 2 0 与 Z3 py 实现 https stackoverflow com questions 13826217 z3 smt 2 0 vs z3 py implementation我实现了无穷大正实
  • 根据求解器的决定执行 get-model 或 unsat-core

    我想知道 SMT LIB 2 0 脚本中是否有可能访问求解器的最后一个可满足性决策 sat unsat 例如 以下代码 set option produce unsat cores true set option produce model
  • (Z3Py) 声明函数

    我想在简单的 result x t c 公式中找到一些给定结果 x 对的 c 和 t 系数 from z3 import x Int x c Int c t Int t s Solver f Function f IntSort IntSo
  • Z3:检查模型是否唯一

    Z3 有没有办法证明 表明给定模型是唯一的并且不存在其他解决方案 一个小例子来演示 declare const a1 Int declare const a2 Int declare const a3 Int declare const b
  • 使用SMT-LIB使用公式计算模块数量

    我不确定使用 SMT LIB 是否可以做到这一点 如果不可能 是否存在可以做到这一点的替代求解器 考虑方程 a lt 10 and a gt 5 b lt 5 and b gt 0 b lt c lt a with a b and c整数
  • 是否可以将一位的位向量转换为 SMTLib2 中的布尔变量?

    我想要一个布尔变量来测试 例如 位向量的第三位是否为 0 位向量的理论允许提取 1 位作为位向量 但不是布尔类型 我想知道我是否可以出演这个角色 谢谢 更新 如果我的问题不清楚 我很抱歉 但 Nikolaj Bjorner 的答案是如何测试
  • Z3 python对待x**2与x*x不同?

    看来Z3 Python接口不喜欢 运算符 它可以处理x x但不能处理x 2 如下例所示 gt gt gt x y x y Reals x y gt gt gt z3 prove Implies x 6 0 x 2 36 0 failed t
  • z3 中的列表串联

    有没有办法在 z3 中连接两个列表 类似于 ML 中的 运算符 我正在考虑自己定义它 但我不认为 z3 支持递归函数定义 即 define fun concat List l1 List l2 List ite isNil l1 l2 co
  • Z3 的简化

    declare datatypes SE BROKEN ON OFF declare const s SE declare const a Int simplify or s ON s OFF s BROKEN simplify and g
  • 如何使用 Z3 SMT-LIB 证明 Frobenius 代数中的定理

    我们在弗罗贝尼乌斯代数中证明以下定理 使用以下代码进行证明 Frobenius algebra object A mu eta delta epsilon declare sort A declare sort AA declare sor

随机推荐