TCS Journal 2023 Journal Article
Towards more efficient methods for solving regular-expression heavy string constraints
- Murphy Berzish
- Joel D. Day
- Vijay Ganesh
- Mitja Kulczynski
- Florin Manea
- Federico Mora
- Dirk Nowotka
Author name cluster
Mitja Kulczynski
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
2 papers
2 author rows
Possible papers
2FormaliSE Conference 2020 Conference Paper
Rule-based Word Equation Solving
- Joel D. Day
- Mitja Kulczynski
- Florin Manea
- Dirk Nowotka
- Danny Bøgsted Poulsen
We present a transformation-system-based technique in the framework of string solving, by reformulating a classical combinatorics on words result, the Lemma of Levi. We further enrich the induced rules by simplification steps based on results from the combinatorial theory of word equations, as well as by the addition of linear length constraints. This transformation-system approach cannot solve all equations efficiently by itself. To improve the efficiency of our transformation-system approach we integrate existing successful string solvers, which are called based on several heuristics. The experimental evaluation we performed shows that integrating our technique as an inprocessing step improves in general the performance of existing solvers.