Publication Details

Solving String Constraints with Lengths by Stabilization

CHEN Yu-Fang, CHOCHOLATÝ David, HAVLENA Vojtěch, HOLÍK Lukáš, LENGÁL Ondřej and SÍČ Juraj. Solving String Constraints with Lengths by Stabilization. Proceedings of the ACM on Programming Languages, vol. 7, no. 10, 2023, pp. 2112-2141. ISSN 2475-1421. Available from: http://dx.doi.org/10.1145/3622872
Czech title
Řešení řetězcových omezení s délkami pomocí stabilizace
Type
journal article
Language
english
Authors
Chen Yu-Fang (ASIN)
Chocholatý David, Ing. (FIT BUT)
Havlena Vojtěch, Ing., Ph.D. (DITS FIT BUT)
Holík Lukáš, doc. Mgr., Ph.D. (DITS FIT BUT)
Lengál Ondřej, Ing., Ph.D. (DITS FIT BUT)
Síč Juraj, Mgr. (DITS FIT BUT)
URL
Keywords

string constraints
SMT solver
stabilization
satisfiability

Abstract

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.

Published
2023
Pages
2112-2141
Journal
Proceedings of the ACM on Programming Languages, vol. 7, no. 10, ISSN 2475-1421
Publisher
Association for Computing Machinery
DOI
UT WoS
001087279100076
EID Scopus
BibTeX
@ARTICLE{FITPUB13093,
   author = "Yu-Fang Chen and David Chocholat\'{y} and Vojt\v{e}ch Havlena and Luk\'{a}\v{s} Hol\'{i}k and Ond\v{r}ej Leng\'{a}l and Juraj S\'{i}\v{c}",
   title = "Solving String Constraints with Lengths by Stabilization",
   pages = "2112--2141",
   journal = "Proceedings of the ACM on Programming Languages",
   volume = 7,
   number = 10,
   year = 2023,
   ISSN = "2475-1421",
   doi = "10.1145/3622872",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/13093"
}
Back to top