Word equations in synergy with regular constraints (extended version)
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F26%3A0197939" target="_blank" >RIV/00216305:26230/26:0197939 - isvavai.cz</a>
Result on the web
<a href="https://link.springer.com/article/10.1007/s10601-025-09379-w" target="_blank" >https://link.springer.com/article/10.1007/s10601-025-09379-w</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s10601-025-09379-w" target="_blank" >10.1007/s10601-025-09379-w</a>
Alternative languages
Result language
angličtina
Original language name
Word equations in synergy with regular constraints (extended version)
Original language description
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.
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)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2025
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
Constraints
ISSN
1383-7133
e-ISSN
1572-9354
Volume of the periodical
30
Issue of the periodical within the volume
May
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
34
Pages from-to
1-34
UT code for WoS article
001492135600001
EID of the result in the Scopus database
2-s2.0-105005597927