A Regular Matching Constraint for String Variables

A Regular Matching Constraint for String Variables

Roberto Amadini, Peter J. Stuckey

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 1868-1875. https://doi.org/10.24963/ijcai.2023/207

Using a regular language as a pattern for string matching is nowadays a common -and sometimes unsafe- operation, provided as a built-in feature by most programming languages. A proper constraint solver over string variables should support most of the operations over regular expressions and related constructs. However, state-of-the-art string solvers natively support only the membership relation of a string variable to a regular language. Here we take a step forward by defining a specialised propagator for the match operation, returning the leftmost position where a pattern can match a given string. Empirical evidences show the effectiveness of our approach, implemented within the constraint programming framework, and tested against state-of-the-art string solvers.
Keywords:
Constraint Satisfaction and Optimization: CSO: Constraint programming
Constraint Satisfaction and Optimization: CSO: Constraint optimization
Constraint Satisfaction and Optimization: CSO: Constraint satisfaction