A Regular Matching Constraint for String Variables

Roberto Amadini; Peter J. Stuckey

IJCAI 2023poster1 citations

A Regular Matching Constraint for String Variables

Abstract

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.

Constraint Satisfaction and Optimization: CSO: Constraint programmingConstraint Satisfaction and Optimization: CSO: Constraint optimizationConstraint Satisfaction and Optimization: CSO: Constraint satisfaction

BibTeX

@inproceedings{ijcai2023p207,
  title     = {A Regular Matching Constraint for String Variables},
  author    = {Amadini, Roberto and Stuckey, Peter J.},
  booktitle = {Proceedings of the Thirty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-23}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Edith Elkind},
  pages     = {1868--1875},
  year      = {2023},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2023/207},
  url       = {https://doi.org/10.24963/ijcai.2023/207},
}