Solving String Constraints with Lengths by Stabilization
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F23%3APU149437" target="_blank" >RIV/00216305:26230/23:PU149437 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1145/3622872" target="_blank" >http://dx.doi.org/10.1145/3622872</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3622872" target="_blank" >10.1145/3622872</a>
Alternative languages
Result language
angličtina
Original language name
Solving String Constraints with Lengths by Stabilization
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Proceedings of the ACM on Programming Languages
ISSN
2475-1421
e-ISSN
—
Volume of the periodical
7
Issue of the periodical within the volume
10
Country of publishing house
US - UNITED STATES
Number of pages
30
Pages from-to
2112-2141
UT code for WoS article
001087279100076
EID of the result in the Scopus database
2-s2.0-85174877465