Word equations in synergy with regular constraints (extended version)
Open Access
- 21 May 2025
- journal article
- research article
- Published by Springer Nature in Constraints
- Vol. 30 (1-4) , 1-34
Abstract
We propose a new automata-based algorithm for solving string constraints that tightly integrates reasoning about equations and regular constraints. Exchanging information between the two allows an efficient pruning of generated combinatorial cases. The algorithm is based on a novel language-based characterization of satisfiability of word equations with regular constraints. Namely, satisfiability of an equation is implied by its stability : the concatenation of the regular languages constraining variables on the left-hand side equals the concatenation of the languages on the right-hand side. It is complete for the chain-free string constraints. We experimentally show that our prototype implementation is competitive with the best string solvers and even superior on difficult examples.Keywords
All Related Versions
Funding Information
- Ministerstvo Školství, Mládeže a Tělovýchovy (LL1908)
- Grantová Agentura České Republiky (GA23-07565S)
- Ministry of Science and Technology, Taiwan (109-2628-E-001-001-MY3)
- Brno University of Technology
This publication has 59 references indexed in Scilit:
- SolCMC: Solidity Compiler’s Model Checker2022
- cvc5: A Versatile and Industrial-Strength SMT Solver2022
- Solving Not-Substring Constraint withFlat Abstraction2021
- An SMT Solver for Regular Expressions and Linear Arithmetic over String Length2021
- A Symbolic Algorithm for the Case-Split Rule in String Constraint Solving2020
- A Decision Procedure for Path Feasibility of String Manipulating Programs with Integer Data Type2020
- Chain-Free String Constraints2019
- On Solving Word Equations Using SAT2019
- A Decision Procedure for String Logic with Quadratic Equations, Regular Expressions and Length Constraints2018
- Precise Analysis of String Expressions2003