A Regular Matching Constraint for String Variables

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.

Authors

• Roberto Amadini
• Peter J. Stuckey Monash University

Keywords

• Constraint Satisfaction and Optimization: CSO: Constraint optimization
• Constraint Satisfaction and Optimization: CSO: Constraint programming
• Constraint Satisfaction and Optimization: CSO: Constraint satisfaction