Detail publikačního výsledku

Solving String Constraints with Lengths by Stabilization

CHEN, Y.; CHOCHOLATÝ, D.; HAVLENA, V.; HOLÍK, L.; LENGÁL, O.; SÍČ, J.

Originální název

Solving String Constraints with Lengths by Stabilization

Anglický název

Solving String Constraints with Lengths by Stabilization

Druh

Článek WoS

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

string constraints
SMT solver
stabilization
satisfiability

Klíčová slova v angličtině

string constraints
SMT solver
stabilization
satisfiability

Autoři

CHEN, Y.; CHOCHOLATÝ, D.; HAVLENA, V.; HOLÍK, L.; LENGÁL, O.; SÍČ, J.

Rok RIV

2024

Vydáno

25.10.2023

ISSN

2475-1421

Periodikum

Proceedings of the ACM on Programming Languages-PACMPL

Svazek

7

Číslo

10

Stát

Spojené státy americké

Strany od

2112

Strany do

2141

Strany počet

30

URL

http://dx.doi.org/10.1145/3622872

BibTex

@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-PACMPL",
  year="2023",
  volume="7",
  number="10",
  pages="2112--2141",
  doi="10.1145/3622872",
  url="http://dx.doi.org/10.1145/3622872"
}