Solving String Constraints with Lengths by Stabilization

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Solving String Constraints with Lengths by Stabilization

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Solving String Constraints with Lengths by Stabilization

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Proceedings of the ACM on Programming Languages

ISSN

2475-1421

e-ISSN

—

Svazek periodika

7

Číslo periodika v rámci svazku

10

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

30

Strana od-do

2112-2141

Kód UT WoS článku

001087279100076

EID výsledku v databázi Scopus

2-s2.0-85174877465