Stochastic Satisfiability Modulo Theories for Non-linear Arithmetic
Stochastic Satisfiability Modulo Theories for Non-linear Arithmetic
复制标题
非线性算术的随机可满足性模理论
DOI：
10.1007/978-3-540-68155-7_20
复制
发表时间：
2008
影响因子：
2.9
通讯作者：
M. Fränzle
中科院分区：
文献类型：
--
作者：
Tino Teige;M. Fränzle
随机可满足模理论（SSMT）问题是SMT问题在存在和随机（即随机）上的推广。SMT公式离散变量上的随机量化。这种扩展允许在不确定性和数据依赖性下结合推理的各种问题的简明描述。求解各种不确定性问题在人工智能领域得到了广泛的研究。著名的例子是随机可满足性和随机约束规划。本文将[FHT08]中关于可判定理论的SSMT算法推广到一般不可判定的实数和整数上的非线性算法理论。因此，我们结合了约束规划的方法，即iSAT算法处理混合布尔和非线性算术约束系统，以及人工智能处理存在和随机量词。此外，我们从概率混合系统领域的基准测试中评估了我们的新算法及其增强。
The stochastic satisfiability modulo theories (SSMT) problem is a generalization of the SMT problem on existential and randomized (aka. stochastic) quantification over discrete variables of an SMT formula. This extension permits the concise description of diverse problems combining reasoning under uncertainty with data dependencies. Solving problems with various kinds of uncertainty has been extensively studied in Artificial Intelligence. Famous examples are stochastic satisfiability and stochastic constraint programming. In this paper, we extend the algorithm for SSMT for decidable theories presented in [FHT08] to non-linear arithmetic theories over the reals and integers which are in general undecidable. Therefore, we combine approaches from Constraint Programming, namely the iSAT algorithm tackling mixed Boolean and non-linear arithmetic constraint systems, and from Artificial Intelligence handling existential and randomized quantifiers. Furthermore, we evaluate our novel algorithm and its enhancements on benchmarks from the probabilistic hybrid systems domain.
影响因子：
3.9
作者：
M. Fränzle;H. Hermanns;Tino Teige
通讯作者：
M. Fränzle;H. Hermanns;Tino Teige