Publication Details
Solving String Constraints with Lengths by Stabilization
Chocholatý David, Ing. (DITS)
Havlena Vojtěch, Ing., Ph.D. (DITS)
Holík Lukáš, doc. Mgr., Ph.D. (DITS)
Lengál Ondřej, Ing., Ph.D. (DITS)
Síč Juraj, Mgr. (DITS)
string constraints
SMT solver
stabilization
satisfiability
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{BUT185210,
author="Yu-Fang {Chen} and David {Chocholatý} and Vojtěch {Havlena} and Lukáš {Holík} and Ondřej {Lengál} and Juraj {Síč}",
title="Solving String Constraints with Lengths by Stabilization",
journal="Proceedings of the ACM on Programming Languages",
year="2023",
volume="7",
number="10",
pages="2112--2141",
doi="10.1145/3622872",
issn="2475-1421",
url="http://dx.doi.org/10.1145/3622872"
}