能够删除特定约束的增量 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中的默认上下文?

    我正在使用 z3py API 4 3 0 我可以轻松翻译一个表达expr从默认上下文到新上下文target ctx using expr translate target ctx 但是我如何从给定的上下文中进行翻译ctx进入默认的 Z3 上
  • 如何让 z3 返回多个 unsat 核心、多个令人满意的作业

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

    我需要一个定理证明器来解决一些简单的线性算术问题 然而 即使是简单的问题我也无法让 Z3 工作 我知道它不完整 但是它应该能够处理这个简单的示例 assert forall t Int t 5 check sat 我不确定我是否忽略了某些事
  • 使用 Z3_solver_get_unsat_core 获取 unsat 核心

    假设这是非线性实数算术的约束集 例如 pred1 gt v2 x v0 x v1 y v0 y v2 y v0 y v1 x v0 x 0 pred2 gt v1 x v0 x v2 y v0 y v1 y v0 y v2 x v0 x 0
  • 将 IR 转换为 Z3 公式?

    我在 IR 中有一些代码 并且该代码已经是 SSA 形式 现在我正在尝试将此代码转换为SMT公式 然后将其提供给Z3进行一些验证 我有一些疑问 有没有技术论文详细解释如何将SSA IR转换为SMT公式 我四处寻找 一无所获 对于那些计算指令
  • 在状态计算中“不断转动曲柄”的有效方法

    我有一个有状态的进程 被建模为i gt RWS r w s a 我想给它一个输入cmds i 目前我做的是批发 let play runGame theGame go where go finished go v n cmds do end
  • Z3 的参考资料 - 它是如何工作的[内部理论]?

    我有兴趣阅读 Z3 背后的内部理论 具体来说 我想了解 Z3 SMT 求解器的工作原理 以及它如何找到不正确模型的反例 我希望能够手动计算出一些非常简单的示例的跟踪 然而 所有 Z3 参考文献似乎都是如何在其中编码 或对其算法的非常高级的描
  • 为什么 Z3 中的运算符“/”和“div”给出不同的结果?

    我试图用两个整数来表示一个实数 并将它们用作实数的分子和分母 我写了以下程序 declare const a Int declare const b Int declare const f Real assert f a b assert
  • 如何将公式转换为析取范式?

    说给定一个公式 t1 gt 2 或 t2 gt 3 且 t3 gt 1 我希望得到它的析取范式 t1 gt 2 且 t3 gt 1 或 t2 gt 3 且 t3 gt 1 在Z3中如何实现这一点 Z3没有将公式转换为DNF的API或策略 然
  • 使用 Z3 SMT 解决谓词演算问题

    我想使用 Z3 来解决最自然地用原子 符号 集合 谓词和一阶逻辑表达的问题 例如 伪代码 A a1 a2 a3 A is a set B b1 b2 b3 C c1 c2 c3 def p a A b B c C gt Bool p is
  • 了解 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 http z3 codeplex com解耦了以下概念Z3 context and Z3 solver The API http research microsoft com en us um redmond projects
  • 目标没有战术支持

    我有一些代码 我想在一些策略的帮助下检查它们 因为我有很多if then else声明 我要申请elim term ite tactic 我使用了以下策略 check sat using then simplify arith lhs tr
  • Z3 实数算术和数据类型理论整合得不太好

    这与我之前问过的问题有关Z3 SMT 2 0 与 Z3 py 实现 https stackoverflow com questions 13826217 z3 smt 2 0 vs z3 py implementation我实现了无穷大正实
  • 为什么 Z3 在这个简单的输入上返回“未知”?

    这是输入 set option auto config false set option mbqi false declare sort T6 declare sort T7 declare fun set23 T7 T7 Bool ass
  • 根据求解器的决定执行 get-model 或 unsat-core

    我想知道 SMT LIB 2 0 脚本中是否有可能访问求解器的最后一个可满足性决策 sat unsat 例如 以下代码 set option produce unsat cores true set option produce model
  • Z3:检查模型是否唯一

    Z3 有没有办法证明 表明给定模型是唯一的并且不存在其他解决方案 一个小例子来演示 declare const a1 Int declare const a2 Int declare const a3 Int declare const b
  • 能够删除特定约束的增量 SMT 求解器

    是否有增量 SMT 求解器或用于某些增量 SMT 求解器的 API 我可以在其中增量添加约束 在其中我可以通过某个标签 名称唯一地标识每个约束 我想唯一地标识约束的原因是这样我可以稍后通过指定标签 名称来删除它们 需要放弃约束是因为我之前的
  • 使用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整数

随机推荐