一句话：提出基于稳定化的字符串约束求解算法，可处理长度约束与不等关系，并集成到 SMT 求解器。
本文研究字符串约束的求解问题，特别是如何在避免组合爆炸的同时处理带线性整数算术长度的约束。作者在将字符串变量解释为语言而非单个字符串的最新词方程与正则约束方法之上，引入稳定化框架，并结合方程对齐与分裂原则来处理长度约束，同时扩展到其他常见字符串约束，包括无限制不等关系，从而覆盖无链片段这一最大可判定类之一。该算法被集成到基于 DPLL 的 SMT 求解器中。在来自字符串程序验证的多个基准上，实现性能与当前最优求解器相当，甚至在若干基准上显著更优。
We present a new algorithm for solving string constraints. The algorithm builds upon a recent method for solving word equations and regular constraints that interprets string variables as languages rather than strings and, consequently, mitigates the combinatorial explosion that plagues other approaches. We extend the approach to handle linear integer arithmetic length constraints by combination with a known principle of equation alignment and splitting, and by extension to other common types of string constraints, yielding a fully-fledged string solver. The ability of the framework to handle unrestricted disequalities even extends one of the largest decidable classes of string constraints, the chain-free fragment. We integrate our algorithm into a DPLL-based SMT solver. The performance of our implementation is competitive and even significantly better than state-of-the-art string solvers on several established benchmarks obtained from applications in verification of string programs.
@article{paperbot1865,
title = {Solving String Constraints with Lengths by Stabilization},
author = {Yu-Fang Chen and David Chocholatý and Vojtěch Havlena and Lukáš Holík and Ondřej Lengál and Juraj Síč},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {OOPSLA2},
year = {2023},
doi = {10.1145/3622872}
}