Přístupnostní navigace
E-application
Search Search Close
Publication detail
HAVLENA, V. CHOCHOLATÝ, D. LENGÁL, O. HOLÍK, L. SÍČ, J. BLAHOUDEK, F. CHEN, Y.
Original Title
Word Equations in Synergy with Regular Constraints
Type
conference paper
Language
English
Original Abstract
We argue that in string solving, word equations and regular constraints are better mixed together than approached separately as in most current string solvers. We propose a fast algorithm, complete for the fragment of chain-free constraints, in which word equations and regular constraints are tightly integrated and exchange information, efficiently pruning the cases generated by each other and limiting possible combinatorial explosion. The algorithm is based on a novel language-based characterisation of satisfiability of word equations with regular constraints. We experimentally show that our prototype implementation is competitive with the best string solvers and even superior in that it is the fastest on difficult examples and has the least number of timeouts.
Keywords
Word equations, regular constraints, string solving, finite automata
Authors
HAVLENA, V.; CHOCHOLATÝ, D.; LENGÁL, O.; HOLÍK, L.; SÍČ, J.; BLAHOUDEK, F.; CHEN, Y.
Released
6. 3. 2023
Publisher
Springer Verlag
Location
Lübeck
ISBN
0302-9743
Periodical
Lecture Notes in Computer Science
Number
14000
State
Federal Republic of Germany
Pages from
403
Pages to
423
Pages count
21
BibTex
@inproceedings{BUT185156, author="Vojtěch {Havlena} and David {Chocholatý} and Ondřej {Lengál} and Lukáš {Holík} and Juraj {Síč} and František {Blahoudek} and Yu-Fang {Chen}", title="Word Equations in Synergy with Regular Constraints", booktitle="Proceedings of FM'23", year="2023", journal="Lecture Notes in Computer Science", number="14000", pages="403--423", publisher="Springer Verlag", address="Lübeck", doi="10.1007/978-3-031-27481-7\{_}23", issn="0302-9743" }