Publication Details

Word Equations in Synergy with Regular Constraints

BLAHOUDEK František, HAVLENA Vojtěch, HOLÍK Lukáš, CHEN Yu-Fang, CHOCHOLATÝ David, LENGÁL Ondřej and SÍČ Juraj. Word Equations in Synergy with Regular Constraints. In: Proceedings of FM'23. Lübeck: Springer Verlag, 2023, pp. 403-423. ISSN 0302-9743.
Czech title
Rovnice nad slovy v součinnosti s regulárními omezeními
Type
conference paper
Language
english
Authors
Blahoudek František, RNDr., Ph.D. (DITS FIT BUT)
Havlena Vojtěch, Ing., Ph.D. (DITS FIT BUT)
Holík Lukáš, doc. Mgr., Ph.D. (DITS FIT BUT)
Chen Yu-Fang (ASIN)
Chocholatý David, Ing. (FIT BUT)
Lengál Ondřej, Ing., Ph.D. (DITS FIT BUT)
Síč Juraj, Mgr. (DITS FIT BUT)
Keywords

Word equations, regular constraints, string solving, finite automata

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.

Published
2023
Pages
403-423
Journal
Lecture Notes in Computer Science, no. 14000, ISSN 0302-9743
Proceedings
Proceedings of FM'23
Conference
25th International Symposium on Formal Methods, Lübeck, DE
Publisher
Springer Verlag
Place
Lübeck, DE
DOI
10.1007/978-3-031-27481-7_23
UT WoS
000999132100023
EID Scopus
2-s2.0-85151053808
BibTeX 
@INPROCEEDINGS{FITPUB12975,
   author = "Franti\v{s}ek Blahoudek and Vojt\v{e}ch Havlena and Luk\'{a}\v{s} Hol\'{i}k and Yu-Fang Chen and David Chocholat\'{y} and Ond\v{r}ej Leng\'{a}l and Juraj S\'{i}\v{c}",
   title = "Word Equations in Synergy with Regular Constraints",
   pages = "403--423",
   booktitle = "Proceedings of FM'23",
   journal = "Lecture Notes in Computer Science",
   number = 14000,
   year = 2023,
   location = "L{\"{u}}beck, DE",
   publisher = "Springer Verlag",
   ISSN = "0302-9743",
   doi = "10.1007/978-3-031-27481-7\_23",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/12975"
}
Back to top